生成給定步數的所有可能的字典組合？

只4個字母（A，B，C，d）用於

說我有出現的字典包括（> = 0）的4個字母

d = {"a":1, "b":2, "c":1, "d":3}

我得到了一個「步驟」號碼。

我想找到所有的字典，可能給出了「步驟」數量的出現減法。

例如

# given the above dictionary and a steps of 2 
moo = {"a":1, "b":1, "c":1, "d":2} 
# moo is a possibility because I simply took away 1 b and 1 d 
# how do I find all the possibilities? (note: occurrences cannot be negative)

編輯：在恰好2個步驟

注步驟：我想找到所有的「哞哞」 S，或全部爲可能提供一個參考詞典的詞典和一些步驟。如果兩本字典符合步驟要求，我不在乎測試。

我想，我想出了一些遞歸代碼來解決這個問題：

def genDict(d, steps): 
    if steps == 0: 
     return [d] 
    dList = [] 
    for key, value in d.items(): 
     if value > 0: 
      temp = dict(d) 
      temp[key] = value -1 
      dList += genDict(temp, steps-1) 
    return dList

任何人都得到不會霸佔內存非遞歸解決方案？

來源

2013-02-28 Derek

恰好兩個「臺階」或最多兩個「臺階」？ – 2013-02-28 07:08:35

@TimPietzcker對不起，我的意思正好2個步驟 – Derek 2013-02-28 07:19:51

我建議你閱讀彼得·諾維格的Python的拼寫校正。它包括計算「編輯距離」的代碼，也許你可以從中得到一些有用的想法。如果您的字典總是使用單個字母作爲鍵，那麼您可以將字典編碼爲字符串，也許只需使用此代碼即可！ http://norvig.com/spell-correct.html – steveha 2013-02-28 07:42:32

如果我正確理解你的問題......

獲取從字典中的整個字符串。

d = {"a":1, "b":2, "c":1, "d":3} 
my_string = "" 
for key, value in d.iteritems(): 
    my_string += key * value 
# my_string now contains 1 a, 2 b's, 1 c, and 3 d's.

使用itertools.permutations得到該字符串的所有可能的排列。

from itertools import permutations 
for i in permutations(my_string): 
    print i # Do something meaningful with the output

來源

2013-02-28 07:10:05 Makoto

您還需要包含已刪除的字符串。 '排列（my_string，len（my_string）-j）在xrange（steps）'中的j – zz3599 2013-02-28 07:32:14

它do't使用的許多記憶，因爲它改變了遞歸相同的列表，但是如果你想收集的結果，而不是僅僅打印出來，你需要追加d的deepcopy的到結果列表。

d = map(list, {"a":1, "b":2, "c":1, "d":3}.items()) 
step = 2 
def choose(d, pos, step): 
    if step == 0: 
     print d 
     return 
    if d[pos][1] > 0: 
     d[pos][1] -= 1 
     choose(d, pos, step-1) 
     d[pos][1] += 1 
    if pos < len(d)-1: 
     choose(d, pos+1, step) 
choose(d, 0, 2)

此輸出：

[['a', 0], ['c', 0], ['b', 2], ['d', 3]] 
[['a', 0], ['c', 1], ['b', 1], ['d', 3]] 
[['a', 0], ['c', 1], ['b', 2], ['d', 2]] 
[['a', 1], ['c', 0], ['b', 1], ['d', 3]] 
[['a', 1], ['c', 0], ['b', 2], ['d', 2]] 
[['a', 1], ['c', 1], ['b', 0], ['d', 3]] 
[['a', 1], ['c', 1], ['b', 1], ['d', 2]] 
[['a', 1], ['c', 1], ['b', 2], ['d', 1]]

來源

2013-02-28 07:24:32 HYRY

生成給定步數的所有可能的字典組合？

回答

相關問題