生成给定步数的所有可能的字典组合？

问题描述：

只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 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

您还需要包含已删除的字符串。 '排列（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]]

生成给定步数的所有可能的字典组合？

相关推荐