动态锁大小的锁组合 [英] Lock Combinations for dynamic lock size
问题描述
下面我将给出两个具有不同维度值的例子.
In the following I will give two examples that have different dimension values.
Lock-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
所以我对所有可能性的期望是
So what I would expect for all of my posibilities is
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
我的第二把锁有以下值:
My second lock has the following values:
numbers = 3
values = 3
所以我期望我的可能性看起来像这样
So what I would expect as my posibilities would look like this
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 过载来生成行.我发现最后两行总是以相同的方式构建.所以我写了一个为我构建它的函数:
I know this can be done with itertools.permutations and so on, but I want to generate the rows by building them and not by overloading my RAM. I figured out that the last 2 rows are always building up the same way.
So I wrote a funtion which builds it for me:
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 现在看起来像这样:
Now I want some kind of way to fit the other values dynamically around my function, so e.g. Lock - 2 would now look like this:
0 posibilities(3)
1 posibilities(2)
2 posibilities(1)
3 posibilities(0)
我知道我应该使用 while 循环等等，但我无法得到动态值的解决方案.
I know I should use a while loops and so on, but I can't get the solution for dynamic values.
推荐答案
您可以递归地执行此操作，但通常最好避免在 Python 中使用递归，除非您确实需要例如，在处理递归数据结构(如树)时.标准 Python(又名 CPython)中的递归效率不高，因为它不能消除尾调用.此外，它还应用了递归限制(默认为 1000 级，但可由用户修改).
You could do this recursively, but it's generally best to avoid recursion in Python unless you really need it, eg, when processing recursive data structures (like trees). Recursion in standard Python (aka CPython) is not very efficient because it cannot do tail call elimination. Also, it applies a recursion limit (which is by default 1000 levels, but that can be modified by the user).
您想要生成的序列被称为弱组合，维基百科文章给出了一个简单的算法，在标准的帮助下很容易实现 itertools.combinations 函数.
The sequences that you want to generate are known as weak compositions, and the Wikipedia article gives a simple algorithm which is easy to implement with the help of the standard itertools.combinations function.
#!/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 位机器上在大约 1.6 秒内生成 170544 个 compositions(15, 8) 序列，在 Python 3.6 或 Python 2.6 上运行.(时间信息是通过使用 Bash time 命令获取的).
FWIW, the above code can generate the 170544 sequences of compositions(15, 8) in around 1.6 seconds on my old 2GHz 32bit machine, running on Python 3.6 or Python 2.6. (The timing information was obtained by using the Bash time command).
FWIW，这是从用户 3736966 的这个答案中提取的递归版本.我已经修改它以使用与我的代码相同的参数名称，使用列表而不是元组，并与 Python 3 兼容.
FWIW, here's a recursive version taken from this answer by user3736966. I've modified it to use the same argument names as my code, to use lists instead of tuples, and to be compatible with 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 秒.
Somewhat surprisingly, this one is a little faster than the original version, clocking in at around 1.5 seconds for compositions(15, 8).
如果您的 Python 版本不理解 yield from，您可以这样做:
If your version of Python doesn't understand yield from, you can do this:
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):.
To generate the compositions in descending order, simply reverse the range call, i.e. for i in range(num + 1):.
最后，这是一个不可读的单行版本.:)
Finally, here's an unreadable one-line version. :)
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是用 C 编写，因此它比文档中显示的大致等效的 Python 代码运行得更快.
Being an inveterate tinkerer, I couldn't stop myself from making yet another version. :) This is simply the original version combined with the code for combinations listed in the itertools docs. Of course, the real itertools.combinations is written in C so it runs faster than the roughly equivalent Python code shown in the docs.
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 秒.
This version is about 50% slower than the original at doing compositions(15, 8): it takes around 2.3 seconds on my machine.
这篇关于动态锁大小的锁组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
