锁组合，用于动态锁大小

锁组合，用于动态锁大小

您 可以 递归执行此 *** 作，但是通常最好避免在Python中进行递归，除非您 确实
需要，例如在处理递归数据结构（例如树）时。标准Python（又名CPython）中的递归效率不高，因为它无法进行尾部调用消除。此外，它还应用了递归限制（默认情况下为1000个级别，但用户可以修改）。

要生成的序列称为弱组合，而Wikipedia文章提供了一种简单的算法，该算法易于在标准

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 combinationsdef 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)]# testfor 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，以上代码可以

compositions(15, 8)

在运行于Python 3.6或Python 2.6的旧2GHz
32位计算机上，在约1.6秒内生成170544个序列。（时序信息是通过使用Bash

time

命令获得的）。

---

FWIW，这是user3736966从此答案中获取的递归版本。我已经对其进行了修改，以使用与代码相同的参数名称，使用列表而不是元组，并与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]

出乎意料的是，此版本比原始版本快一点，大约要花1.5秒

compositions(15, 8)

。

如果您的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]]

---

作为一个顽固的修补匠，我无法阻止自己制作另一个版本。:)这只是原始版本

combinations

，以及itertools文档中列出的代码。当然，实数

itertools.combinations

是用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)]

这个版本比原始版本慢50％

compositions(15, 8)

：在我的机器上大约需要2.3秒。