如何获得列表元素的所有可能组合？

Question

我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合.

我发现了一些代码(通过谷歌搜索)显然正在寻找我正在寻找的东西,但我发现代码相当不透明并且对使用它很谨慎.另外我觉得必须有一个更优雅的解决方案.

我发生的唯一事情就是循环遍历十进制整数1-32768并将它们转换为二进制,并使用二进制表示作为过滤器来选择适当的数字.

有谁知道更好的方法？使用map(),也许？

Answer 1

这个答案错过了一个方面:OP要求所有组合...而不仅仅是长度"r"的组合.

所以你要么必须遍历所有长度"L":

import itertools

stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print(subset)

或者 - 如果你想变得时髦(或者在你之后读取你的代码的大脑弯曲) - 你可以生成"combination()"生成器链,并迭代:

from itertools import chain, combinations
def all_subsets(ss):
    return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))

for subset in all_subsets(stuff):
    print(subset)

Answer 2

看看itertools.combinations:

itertools.combinations(iterable, r)

返回输入iterable中元素的r个子序列.

组合以字典排序顺序发出.因此,如果对输入iterable进行排序,则将按排序顺序生成组合元组.

从2.6开始,包括电池!

Answer 3

这是一个懒惰的单行,也使用itertools:

from itertools import compress, product

def combinations(items):
    return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
    # alternative:                      ...in product([0,1], repeat=len(items)) )

这个答案背后的主要思想是:有2 ^ N个组合 - 与长度为N的二进制字符串的数量相同.对于每个二进制字符串,您选择对应于"1"的所有元素.

items=abc * mask=###
 |
 V
000 -> 
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

需要考虑的事项:

• 这就需要你可以调用len(...)的items(解决方法:如果items是像就像一台发电机的迭代,用第一把它变成一个列表items=list(_itemsArg))
• 这要求迭代的顺序items不是随机的(解决方法:不要疯狂)
• 这就要求项目是独一无二的,要不然{2,2,1}并{2,1,1}都将崩溃{2,1}(解决方法:使用collections.Counter作为一个下拉更换set;它基本上是一个多集...尽管你可能需要在以后使用tuple(sorted(Counter(...).elements())),如果你需要它是可哈希)

演示

>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]

>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]

Answer 4

在@Dan H 高度评价的回答中的评论中,提到powerset()了itertools文档中的配方- 包括Dan本人的一个.但是,到目前为止还没有人发布它作为答案.因为这可能是解决问题的最好方法之一 - 并且考虑到另一位评论者的一点鼓励,如下所示.该函数生成每个可能长度的列表元素的所有唯一组合(包括那些包含零和所有元素的组合).

注意:如果,微妙的不同,目标是获得独特元素的唯一组合,改线s = list(iterable),以s = list(set(iterable))消除任何重复的元素.无论如何,这iterable最终变成了一种list手段,它将与发电机一起工作(与其他几个答案不同).

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)  # allows duplicate elements
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
    print('combo #{}: {}'.format(i, combo))

输出:

combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)

Answer 5

这是一个使用递归:

>>> import copy
>>> def combinations(target,data):
...     for i in range(len(data)):
...         new_target = copy.copy(target)
...         new_data = copy.copy(data)
...         new_target.append(data[i])
...         new_data = data[i+1:]
...         print new_target
...         combinations(new_target,
...                      new_data)
...                      
... 
>>> target = []
>>> data = ['a','b','c','d']
>>> 
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']

Answer 6

这个单行程序为您提供所有组合(如果原始列表/集合包含不同的元素之间的项目0和n项目n)并使用本机方法itertools.combinations:

Python 2

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])

Python 3

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], [])

输出将是:

[[],
 ['a'],
 ['b'],
 ['c'],
 ['d'],
 ['a', 'b'],
 ['a', 'c'],
 ['a', 'd'],
 ['b', 'c'],
 ['b', 'd'],
 ['c', 'd'],
 ['a', 'b', 'c'],
 ['a', 'b', 'd'],
 ['a', 'c', 'd'],
 ['b', 'c', 'd'],
 ['a', 'b', 'c', 'd']]

在线试用:

http://ideone.com/COghfX

Answer 7

我同意Dan H的观点,Ben确实要求所有组合.itertools.combinations()没有给出所有组合.

另一个问题是,如果输入可迭代很大,那么返回生成器而不是列表中的所有内容可能更好:

iterable = range(10)
for s in xrange(len(iterable)+1):
  for comb in itertools.combinations(iterable, s):
    yield comb

Answer 8

您可以使用这个简单的代码在python中生成列表的所有组合

import itertools

a = [1,2,3,4]
for i in xrange(0,len(a)+1):
   print list(itertools.combinations(a,i))

结果将是:

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

Answer 9

我想我会为那些寻求答案的人添加这个功能,而无需导入itertools或任何其他额外的库.

def powerSet(items):
    """
    Power set generator: get all possible combinations of a list’s elements

    Input:
        items is a list
    Output:
        returns 2**n combination lists one at a time using a generator 

    Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
    """

    N = len(items)
    # enumerate the 2**N possible combinations
    for i in range(2**N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

简单的Yield Yield用法:

for i in powerSet([1,2,3,4]):
    print (i, ", ",  end="")

以上用法示例的输出:

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

Answer 10

这种方法可以轻松地转移到所有支持递归的编程语言中（无itertools，无收益，无列表理解）：

def combs(a):
    if len(a) == 0:
        return [[]]
    cs = []
    for c in combs(a[1:]):
        cs += [c, c+[a[0]]]
    return cs

>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

Answer 11

这是另一个解决方案(单线程),涉及使用itertools.combinations函数,但在这里我们使用双列表理解(而不是for循环或求和):

def combs(x):
    return [c for i in range(len(x)+1) for c in combinations(x,i)]

演示:

>>> combs([1,2,3,4])
[(), 
 (1,), (2,), (3,), (4,), 
 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), 
 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), 
 (1, 2, 3, 4)]

Answer 12

from itertools import permutations, combinations


features = ['A', 'B', 'C']
tmp = []
for i in range(len(features)):
    oc = combinations(features, i + 1)
    for c in oc:
        tmp.append(list(c))

输出

[
 ['A'],
 ['B'],
 ['C'],
 ['A', 'B'],
 ['A', 'C'],
 ['B', 'C'],
 ['A', 'B', 'C']
]

Answer 13

3个功能：

1. n 个元素列表的所有组合
2. n 个元素的所有组合列表，其中顺序不明确
3. 所有排列

import sys

def permutations(a):
    return combinations(a, len(a))

def combinations(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinations(a[:i] + a[i+1:], n-1):
                yield [a[i]] + x

def combinationsNoOrder(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinationsNoOrder(a[:i], n-1):
                yield [a[i]] + x
    
if __name__ == "__main__":
    for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])):
        print(s)

Answer 14

我喜欢这个问题，因为有很多方法可以实现它。我决定为未来创建一个参考答案。

生产中用什么？

intertools 的文档有一个独立的示例，为什么不在您的代码中使用它呢？有些人建议使用more_itertools.powerset，但它具有完全相同的实现！如果我是你，我不会为了一件小事而安装整个软件包。也许这是最好的方法：

import itertools

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

其他可能的方法

方法 0：使用组合

import itertools

def subsets(nums):
    result = []
    for i in range(len(nums) + 1):
        result += itertools.combinations(nums, i)
    return result

方法 1：直接递归

def subsets(nums):
    result = []

    def powerset(alist, index, curr):
        if index == len(alist):
            result.append(curr)
            return

        powerset(alist, index + 1, curr + [alist[index]])
        powerset(alist, index + 1, curr)

    powerset(nums, 0, [])
    return result

方法 2：回溯

def subsets(nums):
    result = []

    def backtrack(index, curr, k):
        if len(curr) == k:
            result.append(list(curr))
            return
        for i in range(index, len(nums)):
            curr.append(nums[i])
            backtrack(i + 1, curr, k)
            curr.pop()

    for k in range(len(nums) + 1):
        backtrack(0, [], k)
    return result

或者

def subsets(nums):
    result = []

    def dfs(nums, index, path, result):
        result.append(path)
        for i in range(index, len(nums)):
            dfs(nums, i + 1, path + [nums[i]], result)

    dfs(nums, 0, [], result)
    return result

方法 3：位掩码

def subsets(nums):
    res = []
    n = len(nums)
    for i in range(1 << n):
        aset = []
        for j in range(n):
            value = (1 << j) & i  # value = (i >> j) & 1
            if value:
                aset.append(nums[j])
        res.append(aset)
    return res

或者（不是真正的位掩码，凭直觉知道正好有 2^n 个子集）

def subsets(nums):
    subsets = []
    expected_subsets = 2 ** len(nums)

    def generate_subset(subset, nums):
        if len(subsets) >= expected_subsets:
            return
        if len(subsets) < expected_subsets:
            subsets.append(subset)
        for i in range(len(nums)):
            generate_subset(subset + [nums[i]], nums[i + 1:])

    generate_subset([], nums)
    return subsets

方法 4：级联

def subsets(nums):
    result = [[]]
    for i in range(len(nums)):
        for j in range(len(result)):
            subset = list(result[j])
            subset.append(nums[i])
            result.append(subset)
    return result

Answer 15

您还可以使用优秀软件包中的powerset功能more_itertools。

from more_itertools import powerset

l = [1,2,3]
list(powerset(l))

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

我们还可以验证它是否符合 OP 的要求

from more_itertools import ilen

assert ilen(powerset(range(15))) == 32_768

Answer 16

下面是一个“标准递归答案”，类似于其他类似的答案/sf/answers/1662058751/。（我们实际上不必担心堆栈空间不足，因为我们无法处理所有 N！个排列。）

它依次访问每个元素，要么获取它，要么离开它（我们可以从该算法中直接看到 2^N 基数）。

def combs(xs, i=0):
    if i==len(xs):
        yield ()
        return
    for c in combs(xs,i+1):
        yield c
        yield c+(xs[i],)

演示：

>>> list( combs(range(5)) )
[(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)]

>>> list(sorted( combs(range(5)), key=len))
[(), 
 (0,), (1,), (2,), (3,), (4,), 
 (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3), 
 (2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2), 
 (3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1), 
 (4, 3, 2, 1, 0)]

>>> len(set(combs(range(5))))
32

Answer 17

我知道使用 itertools 来获取所有组合要实用得多，但是如果您碰巧希望编写大量代码，则可以仅通过列表理解来部分实现此目的

对于两对的组合：

lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]

而且，对于三对的组合，就像这样简单：

lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]]

结果与使用 itertools.combinations 相同：

import itertools
combs_3 = lambda l: [
    (a, b, c) for i, a in enumerate(l) 
    for ii, b in enumerate(l[i+1:]) 
    for c in l[i+ii+2:]
]
data = ((1, 2), 5, "a", None)
print("A:", list(itertools.combinations(data, 3)))
print("B:", combs_3(data))
# A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
# B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]