動態鎖定大小的鎖組合

以下我將給出具有不同維數值的兩個示例。動態鎖定大小的鎖組合

鎖定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我的榮幸！如果您有興趣，我已經在我的答案中添加了我在其他地方找到的遞歸解決方案。儘管我之前說過，遞歸解決方案應該沒問題。 –

動態鎖定大小的鎖組合

回答

相關問題