生成列表的所有可能组合

Question

我需要能够创建一个包含输入列表中所有可能组合的列表。 例如，列表[1,2,3]应返回[1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] 列表不必按任何特定顺序排列。在此站点上，我找到了很多使用itertools的函数，但这些函数返回对象，而我只需要一个list。

- Dean

---

这回答解决了你的问题吗？如何获取列表元素的所有可能组合？ - AMC

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]]

- Óscar López

---

这不是OP所问的。 - juliomalegria

@julio.alegria 是的，那就是 OP 所问的，我刚刚编辑了我的答案。 - Óscar López

那很好用，而且返回的结果接近我想要的。有没有办法得到一个列表的列表，而不是元组？ - Dean

@Charles，我刚刚编辑了我的回答，我相信现在它就是你所问的。不要让负评误导你 :) 它们是在我扩展第一个答案之前投出的。 - Óscar López

我不明白为什么 @juliomalegria 给这个点赞负评了，非常无礼！一开始的回答是错误的，但 Oscar 更正了回答，现在它有效了。请取消点赞负评。优雅而简洁的解决方案！+1 :) - pmalbu

Answer 2

itertools 模块确实返回生成器而不是列表，但是：

• 生成器通常比列表更有效率（特别是当你需要生成大量的组合时）
• 当你真正需要时，你可以随时使用 list(...) 将生成器转换为列表。

itertools 的 chain 和 combinations 函数很好用，但是需要使用 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

请注意，在任何情况下，迭代所有组合仍需要一些时间，但如果您尽早找到所需内容，则可以获得很大的收益。

- Arel

---

这应该是被接受的答案。尽管可能更难跟踪，但它是您能找到的最有效使用生成器的方法。对于大型列表来说，内存效率要高得多。 - b10hazard

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)

- Andrew Clark

---

我尝试使用这个，但解释器说我不能在NoneType上使用iter。 - Dean

你的两个解决方案仍然返回元组列表。 - juliomalegria

是的，我需要一个列表的列表，而不是元组。有没有一种方法可以在不使用itertools的情况下解决这个问题？ - Dean

@Charles，您可以不使用itertools来解决它，但这将会更加困难。将元组转换为列表非常容易，而且元组与列表几乎完全相同，因此我怀疑您真的需要这样做。如果您遇到错误，请向我们展示代码未能正常执行的情况。否则我们无法找出您的问题所在。 - Winston Ewert

@Charles - 我修改了我的代码，用于将元组转换为列表，并将单个长度的元组转换为与您示例中相同的值。这可以在不使用itertools的情况下完成，但不会像itertools那样简洁。 - Andrew Clark

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]]

编辑：combinations函数的第一个参数是可迭代对象，第二个参数是生成元组的长度（在这个例子中从1到len(l)）。

更多关于combinations的信息：http://docs.python.org/library/itertools.html#itertools.combinations

- juliomalegria

Answer 5

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

如果您想要一条指令。

- Prafulla Mahesh Pallal

Answer 6

我认为可以将其他答案简化成一个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)]

- Ninjakannon