动态锁定大小的锁组合
以下我将给出具有不同维数值的两个示例。动态锁定大小的锁组合
锁定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
那么我希望我所有的posibilities的是
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
所以我会期待,因为我的posibilities看起来像这样
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来生成行。我发现最后2行始终以相同的方式构建。 所以我写了它建立它为我funtion:
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
现在我想某种方式,以适应动态在我的函数的其他值,所以如锁 - 2现在是这样的:
0 posibilities(3)
1 posibilities(2)
2 posibilities(1)
3 posibilities(0)
我知道我应该使用while
循环等等,但我不能获得动态值的解决方案。
您可以做这个递归,但它通常最好避免在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秒我的机器上。
感谢您的尾巴电话的链接。学到的东西。 –
哇!非常感谢。这正是我正在寻找的。 –
@ fab-da-boy我的荣幸!如果您有兴趣,我已经在我的答案中添加了我在其他地方找到的递归解决方案。尽管我之前说过,递归解决方案应该没问题。 –
你为什么认为itertools填满你的内存?它专门设计成一个懒惰的迭代器,它不会一次创建所有排列。 – jonrsharpe
@jonrsharpe其实我们试过了。而且我们自己的解决方案花费了更长的时间。 –
这与填满内存不同,尽管... – jonrsharpe