-1

係数の組み合わせを作成するのに問題があります。基本的に私はアイテムのリストを持っており、次のようにそれらの係数のすべての一意の組み合わせを取得したいと思います。

dog:1 cat:1
dog:2 cat:1
dog:3 cat:1
dog:1 cat:2
dog:2 cat:2

これを行うための最良の方法（動的計画法、再帰、ブルートフォースなど）がよくわからないため、再帰を実行することから始めようとしました。

list = ["dog", "cat"]

coeff = [1] * len(list)
main_queue = []

def recursion(k, list):
    for item in list[0:k-1]:
        for data in range(5):
            coeff_temp = coeff
            coeff_temp[k] = data
            main_queue.append(coeff_temp)
            #print item, data

    if k == (len(list)-1):
        return
    else:
        recursion(k+1, list)

recursion(0, list)

print "*" * 30

for x in main_queue:
    print x

出力は次のとおりです。

******************************
[4, 1]
[4, 1]
[4, 1]
[4, 1]
[4, 1]

メインキューの最後のエントリのみを変更します。私は何が間違っているのですか？

psこれを行うための最良の方法ですか（範囲は1〜5で、リストには約20〜30の項目があります。動的計画法を使用する方がよいでしょう）。

4

5 に答える 5

2 
data = ["dog", "cat"]
upto = 4

def all_combos(items, upto):
    if items < 1:
        yield []
    else:
        for r in range(upto+1):
            for rest in all_combos(items-1, upto):
                yield [r] + rest

for coeffs in all_combos(len(data), upto):
    print ", ".join("{}s: {}".format(n, coeff) for n,coeff in zip(data,coeffs))

結果は

dogs: 0, cats: 0
dogs: 0, cats: 1
dogs: 0, cats: 2
dogs: 0, cats: 3
dogs: 0, cats: 4
dogs: 1, cats: 0
dogs: 1, cats: 1
dogs: 1, cats: 2
dogs: 1, cats: 3
dogs: 1, cats: 4
dogs: 2, cats: 0
dogs: 2, cats: 1
dogs: 2, cats: 2
dogs: 2, cats: 3
dogs: 2, cats: 4
dogs: 3, cats: 0
dogs: 3, cats: 1
dogs: 3, cats: 2
dogs: 3, cats: 3
dogs: 3, cats: 4
dogs: 4, cats: 0
dogs: 4, cats: 1
dogs: 4, cats: 2
dogs: 4, cats: 3
dogs: 4, cats: 4

それがあなたが求めているものです。組み合わせの数は、データが増えるにつれて爆発的に増加することを覚えておいてください。(len(data))**upto

編集：指摘されているように、これを達成する別の方法は

from itertools import product

def all_combos(items, upto):
    return product(*(range(upto+1) for i in range(items)))
于 2012-05-22T16:42:55.990 に答える
1

あなたの間違いはこの行です：

coeff_temp = coeff

coeff同じオブジェクトへの参照を作成する：のコピーは作成されません。次の行で変更する場合：

coeff_temp[k] = data

これまでに挿入したものをすべて変更しています-それらはすべて同じリストです！

リストを実際にコピーするには、次を使用します。

coeff_temp = list(coeff)

また

coeff_temp = coeff[:]

これがあなたの問題に対する最良の解決策です：

import itertools
data = {
    "dog": xrange(1, 5),
    "cat": xrange(1, 5)
    #add more here...
}
combinations = (dict(zip(data.keys(), c)) for c in itertools.product(*data.values()))

for c in combinations:
    print c
于 2012-05-22T16:29:25.183 に答える
1

必要なのはN桁のベースM番号であるように見えます。ここで、Nはリスト内の項目の数であり、Mはそれぞれの可能な値の数です。

たとえば、リストに3つの項目があり、それぞれに1から4までの値が必要な場合は、3桁の基数3の数値を使用します。最初の桁はですので1、リスト項目に割り当てるときに各桁に1を追加します。

この場合、最初の列は数えたときの実際の数であり、2番目の列は同じ数であり、各桁に1が追加され、次に3匹の動物のそれぞれに値が割り当てられます。

000   111     cat 1 dog 1 hamster 1
001   112     cat 1 dog 1 hamster 2
002   113     cat 1 dog 1 hamster 3
010   121     cat 1 dog 2 hamster 1
011   122     cat 1 dog 2 hamster 2
012   123     cat 1 dog 2 hamster 3
020   131     cat 1 dog 3 hamster 1
021   132     cat 1 dog 3 hamster 2
022   133     cat 1 dog 3 hamster 3
100   211     cat 2 dog 1 hamster 1

残りの3桁の基数3の数値についても同様です。

于 2012-05-22T16:42:57.310 に答える
0

itertools lib http://docs.python.org/library/itertools.htmlを見てみてください。combinations （）関数があります。これは役立つはずです。

于 2012-05-22T16:21:52.130 に答える
0

組み合わせが必要な場合は、ほとんどの場合、再帰が正解です。

コードに問題があります。関数内で、への参照をコピーしているrecursionと言うと、毎回同じリストを追加しているだけです。それが理由です 。そうでなければ、この方法は私には問題ないようです。coeff_temp = coeffcoeff

行を変更します

coeff_temp = coeff

に

coeff_temp = list(coeff)

リストをコピーして、そこから続けます。

itertoolsモジュールは、組み合わせに最適なソリューションです。

于 2012-05-22T16:27:10.773 に答える