Сгенерировать все возможные комбинации словарей с заданным количеством шагов?

Question

Предположим:

только 4 буквы (а, б, в, г) используются

Скажем, у меня есть словарь содержат вхождений (> = 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 шагах

Примечание: Я хочу найти все «МОО» ю.ш., или все словари, которые можно дается ссылка словарь и несколько шагов. Меня не волнует тестирование, если два словаря соответствуют требованиям шага.

Я думаю, что я придумал какой-то рекурсивный код, чтобы решить эту проблему:

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 

Любых получил нерекурсивное решение, которое не будет Hog памяти?

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

Он do't использовать много памяти, потому что изменить один и тот же список в рекурсии, однако, если вы хотите, чтобы собрать результат вместо того, чтобы просто распечатать его, вам нужно добавить к 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]]