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

Question

假设：

我们只使用4个字母（a、b、c、d）

假设我有一个字典，里面记录了这4个字母出现的次数（次数大于等于0）。

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步。

注意：我想找到所有的“moo”，或者说找到所有可能的字典，这些字典是基于一个参考字典和一个步骤数字生成的。我不关心两个字典是否满足步骤的要求。

我想我写了一些递归代码来解决这个问题：

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

有没有人能提供一个非递归的解决方案，这样不会占用太多内存？

Answer 1

如果我理解你的问题没错的话...

1. 从字典中获取完整的字符串。

   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.
   

2. 使用 itertools.permutations 来获取这个字符串的所有可能排列。

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

Answer 2

它不会占用很多内存，因为在递归过程中它是修改同一个列表。不过，如果你想把结果收集起来，而不仅仅是打印出来，你需要把列表d的一个深拷贝添加到结果列表中。

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