最大组合数

Question

我正在尝试生成一个包含四个数字的所有可能组合的列表，数字范围是从0到9。

我快要成功了，但输出的结果没有显示从0000到9999的每一个可能组合。

有没有什么线索可以告诉我，下面的代码为什么会漏掉某些组合呢？

def permgen(items, n):
  if n==0: yield []
    else:
        for i in range(len(items)):
            for cc in permgen(items[:i]+items[i+1:],n-1):
                yield [items[i]]+cc

if __name__=="__main__":
    for c in permgen(['0','1','2','3','4','5','6','7','8','9'],4): print ''.join(c)

Answer 1

看看这个itertools的组合生成器：

>>> from itertools import combinations, permutations, product
>>> def pp(chunks):
...     print(' '.join(map(''.join, chunks)))
...
>>> pp(combinations('012', 2))
01 02 12
>>> pp(permutations('012', 2))
01 02 10 12 20 21
>>> pp(product('012', repeat=2))
00 01 02 10 11 12 20 21 22
>>> from itertools import combinations_with_replacement
>>> pp(combinations_with_replacement('012', 2))
00 01 02 11 12 22

combinations_with_replacement 在Python 3.1（或者2.7）中可以使用。

看起来itertools.product是最适合你这个任务的选择。

Answer 2

如果你使用的是 Python 2.6，那为什么不试试 itertools.combinations 呢？

from itertools import combinations
combinations(range(10), 4)

Answer 3

这一行：

for cc in permgen(items[:i]+items[i+1:],n-1):

你基本上是在说“获取一个数字，然后再加上一个和它不同的数字，重复这个过程n次，然后返回这些数字的列表。”这样做会得到每个数字中没有重复的数字。如果你把这一行改成：

for cc in permgen(items,n-1):

那么你就会得到所有的组合。