python - 查找每次删除不同元素的列表的所有组合

标签 python list python-3.x combinations

我需要一种方法来从两个不同的列表中查找所有组合,其中每个元素可能为空也可能不为空。例如,对于两个列表,我想调用一个返回所有这些组合的列表的函数:

a = ['A', 'S', 'B']
b = ['A', 'B']
find_combinations(a, b)

应该返回:

[['A', 'S', 'B'], ['A', 'S'], ['S', 'B'], ['S']]

我可以做这个简单的例子,但如果列表更复杂,比如['A', 'B', 'S', 'A', 'A']那么可能的选项是更复杂:

[['A', 'B', 'S', 'A', 'A'],
 ['A', 'B', 'S', 'A'],
 ['A', 'B', 'S', 'A'],
 ['B', 'S', 'A', 'A']
  ... etc.

最佳答案

我假设b元素是可散列的。在这种情况下,您可以使用以下代码:

def without(a,i,bi,l):
    if i >= len(a):
        yield tuple(l)
    else:
        l.append(a[i])
        for result in without(a,i+1,bi,l):
            yield result
        l.pop()
        if a[i] in bi:
            for result in without(a,i+1,bi,l):
                yield result

def find_combinations(a, b):
    for result in without(a,0,set(b),[]):
        yield result

这里我们首先将b转换为集合以提高性能。严格来说这是没有必要的。然后我们使用递归算法,对于 ab 中的每个元素 a[i],我们有一个决策点:不要将其包含在结果中(这就是为什么我们在弹出该元素时再次执行递归的原因)。当我们到达列表末尾时,我们将运行列表l转换为tuple(..)。您还可以使用 list(..) 将其转换为列表。

我们使用运行列表来稍微提高性能,因为连接两个列表的时间复杂度为O(n),而运行列表可以append(..)pop(..)O(1) 摊销成本。

这将生成一个元组生成器。您可以使用 list(..) 实现每个生成器的结果,例如:

>>> list(find_combinations(['A','S','B'],['A','B']))
[('A', 'S', 'B'), ('A', 'S'), ('S', 'B'), ('S',)]
>>> list(find_combinations(['A', 'B', 'S', 'A', 'A'],['A','B']))
[('A', 'B', 'S', 'A', 'A'), ('A', 'B', 'S', 'A'), ('A', 'B', 'S', 'A'), ('A', 'B', 'S'), ('A', 'S', 'A', 'A'), ('A', 'S', 'A'), ('A', 'S', 'A'), ('A', 'S'), ('B', 'S', 'A', 'A'), ('B', 'S', 'A'), ('B', 'S', 'A'), ('B', 'S'), ('S', 'A', 'A'), ('S', 'A'), ('S', 'A'), ('S',)]

如果需要 list,您可以使用 map(list,..) 将它们转换为列表,例如:

>>> list(map(list,find_combinations(['A','S','B'],['A','B'])))
[['A', 'S', 'B'], ['A', 'S'], ['S', 'B'], ['S']]
>>> list(map(list,find_combinations(['A', 'B', 'S', 'A', 'A'],['A','B'])))
[['A', 'B', 'S', 'A', 'A'], ['A', 'B', 'S', 'A'], ['A', 'B', 'S', 'A'], ['A', 'B', 'S'], ['A', 'S', 'A', 'A'], ['A', 'S', 'A'], ['A', 'S', 'A'], ['A', 'S'], ['B', 'S', 'A', 'A'], ['B', 'S', 'A'], ['B', 'S', 'A'], ['B', 'S'], ['S', 'A', 'A'], ['S', 'A'], ['S', 'A'], ['S']]

关于python - 查找每次删除不同元素的列表的所有组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43032516/

相关文章:

python - 在 Python 中弹出图形对话框的最简单的跨平台方法是什么?

python - 在不使用 .join 的情况下在 input() 提示中打印列表的元素并将列表转换为 str

python - 连接中止 .', BadStatusLine("''",) 在服务器上?

django - 从 Redis 读取和写入数据时不要序列化和反序列化(Pickle 和 Unpickle)数据

Python for 循环声明和行为

python - 在 docker-compose 中运行 Django

python - 在打印功能中包含变量的问题

list - 正确使用 Prolog 中的集合

python/numpy 一次合并 4 行子数组

python - 我如何为我的员工组织健康检查(带有 python 代码的 Docker)?