动态锁定大小的锁组合

以下我将给出具有不同维数值的两个示例。动态锁定大小的锁组合

锁定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的是

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

numbers = 3 
values = 3

所以我会期待，因为我的posibilities看起来像这样

我知道这可以用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循环等等，但我不能获得动态值的解决方案。

来源

2016-11-10 fab-da-boy

你为什么认为itertools填满你的内存？它专门设计成一个懒惰的迭代器，它不会一次创建所有排列。 – jonrsharpe

@jonrsharpe其实我们试过了。而且我们自己的解决方案花费了更长的时间。 –

这与填满内存不同，尽管... – jonrsharpe

您可以做这个递归，但它通常最好避免在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秒我的机器上。

来源

2016-11-11 01:55:56

感谢您的尾巴电话的链接。学到的东西。 –

哇！非常感谢。这正是我正在寻找的。 –

@ fab-da-boy我的荣幸！如果您有兴趣，我已经在我的答案中添加了我在其他地方找到的递归解决方案。尽管我之前说过，递归解决方案应该没问题。 –

动态锁定大小的锁组合

回答

相关问题