动态锁大小的锁组合

Question

在下面我将给出两个具有不同维度值的示例。在

锁-1

# numbers are the shown values on the so in this case: 0,1,2
numbers = 5
# fields are those things i can turn to change my combination
fields = 4

所以我所期望的是

^{pr2}$

我的第二个锁具有以下值：

numbers = 3
values = 3

所以我希望我的能力是这样的

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

我知道这可以通过itertools.permutations等等来完成，但是我想通过构建行而不是通过重载RAM来生成行。我发现最后两排总是以同样的方式建造。 所以我写了一个函数来为我构建它：

def posibilities(value):
    all_pos = []

    for y in range(value + 1):
        posibility = []
        posibility.append(y)
        posibility.append(value)

        all_pos.append(posibility)

        value -= 1

    return all_pos

现在我想用某种方法来动态拟合函数的其他值，例如Lock-2现在看起来是这样的：

0   posibilities(3)
1   posibilities(2)
2   posibilities(1)
3   posibilities(0)

我知道我应该使用while循环等等，但是我不能得到动态值的解决方案。在

Answer 1

您可以递归地执行此操作，但在Python中通常最好避免递归，除非确实需要递归，例如在处理递归数据结构（如树）时。标准Python（aka CPython）中的递归不是很有效，因为它不能进行tail call消除。此外，它还应用了递归限制（默认为1000级，但用户可以修改）。在

您想要生成的序列被称为weak compositions，维基百科文章给出了一个简单的算法，该算法很容易在标准的^{}函数的帮助下实现。在

#!/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)

输出

^{pr2}$

在我的旧的2GHz 32位机器上，上面的代码可以在大约1.6秒内生成compositions(15, 8)的170544个序列，该机器运行在Python3.6或Python2.6上。（定时信息是通过使用Bashtime命令获得的）。在

---

FWIW，这里是用户3736966从this answer获取的递归版本。我对它进行了修改，使其使用与代码相同的参数名，使用列表而不是元组，并且与Python3兼容。在

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秒。在

如果您的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秒。在