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

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

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

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


当前回答

在Python 3中没有itertools,你可以这样做:

def combinations(arr, carry):
    for i in range(len(arr)):
        yield carry + arr[i]
        yield from combinations(arr[i + 1:], carry + arr[i])

其中最初的carry = ""。

其他回答

还可以使用more_itertools包中的powerset函数。

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

我同意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

下面是一个“标准递归答案”,类似于其他类似的答案https://stackoverflow.com/a/23743696/711085。(实际上,我们不必担心耗尽堆栈空间,因为我们没有办法处理所有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

在Python 3中没有itertools,你可以这样做:

def combinations(arr, carry):
    for i in range(len(arr)):
        yield carry + arr[i]
        yield from combinations(arr[i + 1:], carry + arr[i])

其中最初的carry = ""。

这种方法可以很容易地移植到所有支持递归的编程语言中(没有itertools,没有yield,没有列表理解):

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