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" を検索したい、または参照辞書といくつかのステップを指定して可能なすべての辞書を検索したい。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

誰もメモリを占有しない非再帰的なソリューションを手に入れましたか?

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 に答える