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

我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。

我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。

有人知道更好的办法吗?使用map(),也许?


当前回答

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

在生产中使用什么?

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

or

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

其他回答

3个功能:

列出n个元素的所有组合 列出n个元素的所有组合,其中顺序不明确 所有的排列

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)
from itertools import 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']
]

正如James Brady提到的,你的itertools.combination是一个键。但这并不是一个完整的解决方案。

解决方案1

import itertools
def all(lst):
    # ci is a bitmask which denotes particular combination,
    # see explanation below
    for ci in range(1, 2**len(lst)):
        yield tuple(itertools.compress(
            lst,
            [ci & (1<<k) for k in  range(0, len(lst))]
        ))

解决方案2

import itertools
def all_combs(lst):
    for r in range(1, len(lst)+1):
        for comb in itertools.combinations(lst, r):
            yield comb

例子

>>> list(all_combs([1,2,3]))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
>>> len(list(all_combs([1,2,3])))
7
>>> len(list(all_combs(range(0, 15))))
32767
>>> list(all([1,2,3]))
[(1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)]
>>> len(list(all(range(15))))
32767

解释

假设数组A的长度为N,让长度为N的位掩码B表示一个特定的组合C。如果B[i]是1,那么A[i]属于组合C。

方案1说明

所以我们可以遍历所有的位掩码并用这个位掩码过滤源数组A,这可以通过itertools。compress来完成。

方案2说明

...或者,我们可以用组合来表示

现在我们需要考虑这样的情况,当B中只有一个1,然后只有两个1,等等。每种情况都属于特定的组合。 因此,一旦我们组合所有的组合集,我们将得到所有的子序列。

同样,很明显,在这种情况下,所有可能的组合的数量是2^N - 1。当所有B[i]都为零时,我们省略大小写,因为我们假设空集不是一个组合。否则,就不要减去1。

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

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

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

我想我应该为那些寻求答案的人添加这个函数,而不需要导入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 Generator用法:

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