您可以做这个递归,但它通常最好避免在Python递归除非你真的需要它,比如,处理递归数据结构时(如树)。标准Python(又名CPython)中的递归效率不高,因为它不能完成tail call排除。此外,它应用递归限制(默认为1000个级别,但可以由用户修改)。
您想要生成的序列被称为weak compositions,维基百科文章给出了一个简单的算法,该算法在标准itertools.combinations
函数的帮助下很容易实现。
#!/usr/bin/env python3
''' Generate the compositions of num of a given width
Algorithm from
https://en.wikipedia.org/wiki/Composition_%28combinatorics%29#Number_of_compositions
Written by PM 2Ring 2016.11.11
'''
from itertools import combinations
def compositions(num, width):
m = num + width - 1
last = (m,)
first = (-1,)
for t in combinations(range(m), width - 1):
yield [v - u - 1 for u, v in zip(first + t, t + last)]
# test
for t in compositions(5, 4):
print(t)
print('- ' * 20)
for t in compositions(3, 3):
print(t)
输出
[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 0, 3, 2]
[0, 0, 4, 1]
[0, 0, 5, 0]
[0, 1, 0, 4]
[0, 1, 1, 3]
[0, 1, 2, 2]
[0, 1, 3, 1]
[0, 1, 4, 0]
[0, 2, 0, 3]
[0, 2, 1, 2]
[0, 2, 2, 1]
[0, 2, 3, 0]
[0, 3, 0, 2]
[0, 3, 1, 1]
[0, 3, 2, 0]
[0, 4, 0, 1]
[0, 4, 1, 0]
[0, 5, 0, 0]
[1, 0, 0, 4]
[1, 0, 1, 3]
[1, 0, 2, 2]
[1, 0, 3, 1]
[1, 0, 4, 0]
[1, 1, 0, 3]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3, 0]
[1, 2, 0, 2]
[1, 2, 1, 1]
[1, 2, 2, 0]
[1, 3, 0, 1]
[1, 3, 1, 0]
[1, 4, 0, 0]
[2, 0, 0, 3]
[2, 0, 1, 2]
[2, 0, 2, 1]
[2, 0, 3, 0]
[2, 1, 0, 2]
[2, 1, 1, 1]
[2, 1, 2, 0]
[2, 2, 0, 1]
[2, 2, 1, 0]
[2, 3, 0, 0]
[3, 0, 0, 2]
[3, 0, 1, 1]
[3, 0, 2, 0]
[3, 1, 0, 1]
[3, 1, 1, 0]
[3, 2, 0, 0]
[4, 0, 0, 1]
[4, 0, 1, 0]
[4, 1, 0, 0]
[5, 0, 0, 0]
- - - - - - - - - - - - - - - - - - - -
[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]
FWIW,上述代码可以生成我的旧2GHz的32位机器上的compositions(15, 8)
在约160秒170544个序列,关于Python 3.6或Python 2.6运行。 (定时信息是通过使用Bash time
命令获得的)。
FWIW,这里是由user3736966从this answer采取了递归版本。我修改它使用相同的参数名称作为我的代码,而是使用元组的列表,并成为与Python兼容3.
def compositions(num, width, parent=[]):
if width > 1:
for i in range(num, -1, -1):
yield from compositions(i, width - 1, parent + [num - i])
else:
yield parent + [num]
出人意料的是,这个人是比原来的版本快一点,在compositions(15, 8)
的计时时间约为1.5秒。
如果你的Python版本不理解yield from
,你可以这样做:
def compositions(num, width, parent=[]):
if width > 1:
for i in range(num, -1, -1):
for t in compositions(i, width - 1, parent + [num - i]):
yield t
else:
yield parent + [num]
要生成的组成按降序排列,简单地恢复range
呼叫,即for i in range(num + 1):
。
最后,这是一个不可读的单行版本。 :)
def c(n, w, p=[]):
yield from(t for i in range(n,-1,-1)for t in c(i,w-1,p+[n-i]))if w-1 else[p+[n]]
作为一个根深蒂固的工匠,我无法作出另一个版本管不住自己。 :)这只是原始版本与itertools文档中列出的combinations
的代码结合使用。当然,真正的itertools.combinations
是written in C,所以它的运行速度比文档中显示的大致等效的Python代码快。
def compositions(num, width):
r = width - 1
indices = list(range(r))
revrange = range(r-1, -1, -1)
first = [-1]
last = [num + r]
yield [0] * r + [num]
while True:
for i in revrange:
if indices[i] != i + num:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield [v - u - 1 for u, v in zip(first + indices, indices + last)]
这个版本比原来要慢于做compositions(15, 8)
约50%:大约需要2.3秒我的机器上。
你为什么认为itertools填满你的内存?它专门设计成一个懒惰的迭代器,它不会一次创建所有排列。 – jonrsharpe
@jonrsharpe其实我们试过了。而且我们自己的解决方案花费了更长的时间。 –
这与填满内存不同,尽管... – jonrsharpe