制作列表的所有可能组合

Question

我需要能够创建一个包含输入列表的所有可能组合的列表.例如,列表[1,2,3]应该返回[1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] 列表不必具有任何特定顺序.在这个网站上我发现了很多使用它的函数,itertools但是当我只需要一个函数时它们就会返回对象list.

Answer 1

简单地使用itertools.combinations.例如:

import itertools

lst = [1, 2, 3]
combs = []

for i in xrange(1, len(lst)+1):
    combs.append(i)
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.append(els)

现在combs持有这个值:

[1, [[1], [2], [3]], 2, [[1, 2], [1, 3], [2, 3]], 3, [[1, 2, 3]]]

是的,它与您提供的示例输出略有不同,但在该输出中您没有列出所有可能的组合.

我在每个大小的实际列表之前列出组合的大小,如果你需要的只是组合(没有大小,因为它出现在你的示例输出中)然后尝试这些代码的其他版本:

import itertools

lst = [1, 2, 3]
combs = []

for i in xrange(1, len(lst)+1):
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.extend(els)

现在combs持有这个值:

[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Answer 2

该itertools模块确实返回生成器而不是列表,但是:

• 生成器通常比列表更有效(特别是如果您生成大量组合)
• 您始终可以list(...)在需要时将生成器转换为列表.

在chain和combinations职能itertools工作做好,但你需要使用的Python 2.6或更高版本:

import itertools

def all_combinations(any_list):
    return itertools.chain.from_iterable(
        itertools.combinations(any_list, i + 1)
        for i in xrange(len(any_list)))

然后您可以这样调用:

# as a generator
all_combinations([1,2,3])  # --> <itertools.chain at 0x10ef7ce10>

# as a list
list(all_combinations([1,2,3]))  # --> [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

# as a list of lists
[list(l) for l in all_combinations([1,2,3])]  # --> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

如果您之前没有使用过生成器,请注意您循环遍历它们,就像它们是一个列表一样,例如:

# a generator returned instead of list
my_combinations = all_combinations([1,2,3])

# this would also work if `my_combinations` were a list
for c in my_combinations:
    print "Combo", c

"""
Prints:
  Combo (1,)
  Combo (2,)
  Combo (3,)
  Combo (1, 2)
  Combo (1, 3)
  Combo (2, 3)
  Combo (1, 2, 3)
"""

性能差异可能很大.如果你比较性能,你会发现生成器的创建速度要快得多:

# as a generator
all_combinations(range(25))  # timing: 100000 loops, best of 3: 2.53 µs per loop

# as a list
list(all_combinations(range(25)))  # timing: 1 loops, best of 3: 9.37 s per loop

请注意,在任何一种情况下迭代所有组合仍然需要一些时间,但对于您来说这可能是一个巨大的胜利,特别是如果您在早期找到您正在寻找的东西.

Answer 3

itertools模块中的函数返回迭代器.将这些转换为列表所需要做的就是调用list()结果.

但是,由于您需要分别调用itertools.combinations三次(每个不同长度一次),您可以使用list.extend将迭代器的所有元素添加到最终列表中.

请尝试以下方法:

import itertools
in_list = [1, 2, 3]
out_list = []
for i in range(1, len(in_list)+1):
    out_list.extend(itertools.combinations(in_list, i))

或者作为列表理解:

out_list = [c for i in range(len(in_list)) for c in itertools.combinations(in_list, i+1)]

这些将导致以下列表:

[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

如果您想要列表而不是元组,并将单个长度元组转换为该值,则可以执行以下操作:

out_list = [x[0] if len(x) == 1 else list(x) for x in out_list]
# [1, 2, 3, [1, 2], [1, 3], [2, 3], [1, 2, 3]]

或者将单个项目保留为列表:

out_list = map(list, out_list)

Answer 4

您可以使用itertools.combinations循环内部解决问题:

>>> l = [1,2,3]
>>> comb = []
>>> for i in range(len(l)):
...   comb += itertools.combinations(l,i+1)
... 
>>> comb
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

如果你想要它们作为一个列表:

>>> comb_list = [ list(t) for t in comb ]
>>> comb_list
[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

编辑:组合的第一个参数是可迭代的,第二个参数是生成的元组的长度(在这种情况下,从1去往len(l)).

有关组合的更多信息:http://docs.python.org/library/itertools.html#itertools.combinations

Answer 5

我认为值得将这里的其他答案浓缩成一个简单的 Python 3 示例：

from itertools import chain, combinations

def all_combinations(array):
    return chain(*(list(combinations(array, i + 1)) for i in range(len(array))))

这将返回一个可迭代对象，以查看值：

>>> print(list(all_combinations((1, 2, 3))))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Answer 6

l = [1,2,3]
combs = reduce(lambda x, y: list(itertools.combinations(l, y)) + x, range(len(l)+1), [])

如果你想要一个单线。