0

认为：

仅使用 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

任何人都有一个不会占用内存的非递归解决方案？

4

2 回答 2

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]]
于 2013-02-28T07:24:32.373 回答
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
于 2013-02-28T07:10:05.150 回答