动态锁大小的锁组合

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

所以我对我所有的可能性的期望是

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

我的第二把锁有以下值：

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（又名 CPython）中的递归效率不是很高，因为它无法消除尾部调用。此外，它还应用递归限制（默认情况下为 1000 级，但用户可以修改）。

您想要生成的序列被称为弱组合，维基百科文章提供了一个简单的算法，在标准函数的帮助下很容易实现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，上面的代码可以compositions(15, 8)在我的旧 2GHz 32 位机器上（在 Python 3.6 或 Python 2.6 上运行）上生成大约 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]]

作为一个顽固的修补匠，我无法阻止自己制作另一个版本。:) 这只是原始版本与combinationsitertools 文档中列出的代码的结合。当然，realitertools.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 秒。