做一個範圍的係數組合？

我在製作係數組合時遇到了麻煩。基本上我有一個項目清單，並希望得到係數的所有獨特的組合，他們是這樣的：做一個範圍的係數組合？

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]

它只是改變了我提出的主要隊列中的最後一項。我究竟做錯了什麼？

p.s.這是做到這一點的最佳方式（範圍在1-5之間，列表中會有大約20-30個項目..我最好使用動態編程）？

來源

2012-05-22 Error_404

我不明白你的描述你想要完成什麼。 – murgatroid99

請提供一個*完整的例子，以明確指定輸入和預期輸出。 – NPE

@ murgatroid99我有一個預期輸出的例子。你有什麼理解上的麻煩？ –

你的錯誤是這行：

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-22 16:29:25 Eric

謝謝埃裏克，我意識到我犯了另一個錯誤以及我用列表作爲變量，所以我用你的例子，並改變了變量名，但現在我得到一個錯誤'TypeError：'類型'對象是不可迭代的第一個for循環在遞歸函數 –

@Error_404然後你仍然使用'list'作爲變量。 – Eric

你的權利，有一個我錯過的例子。現在看起來好像有些工作，但是有重複的結果。 –

試試看itertools lib http://docs.python.org/library/itertools.html在哪裏可以找到組合（）函數，它必須幫助你。

來源

2012-05-22 16:21:52 Denis

如果你想要組合，那麼遞歸在幾乎所有的時候都是正確的答案。

沒有您的代碼有問題：裏面的recursion功能，當你說coeff_temp = coeff要複製的參考到coeff，所以你的每一次只是追加相同的列表。這就是爲什麼。否則，該方法對我來說似乎很好。

行

coeff_temp = coeff

更改爲

coeff_temp = list(coeff)

複製的清單，並保持從那裏上。

itertools模塊是一個很好的組合解決方案。

來源

2012-05-22 16:27:10

對不起，@Eric已經回答了同樣的問題，因爲我正在撰寫我的答案，所以直到我發佈時纔看到它。信用應該是他的。 –

你剛剛在那裏，而我正在打字 - 看看時間。然而，你的推理是錯誤的 - 「coeff」是全球性的事實是無關緊要的。 – Eric

@Eric：當然，我的解釋還不夠清楚。我正在試着說完全一樣的你，他使用了對同一個列表的引用。我現在看到它不是很清楚，我已經修復了它。感謝您的評論。 –

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-22 16:42:55

'itertools.product'不會是一個更簡單的方法來獲得這個輸出嗎？（我對OP想要的內容普遍存在困惑;給出的例子與他後來的評論不符。） – DSM

謝謝Hugh這個作品，而且是我想要的。 –

@DSM：當然。看我的答案如何使用它。 – Eric

在我看來，你需要的是一個N位基-M數，其中N是多少的項目在列表中，M是每個可能值的數量。例如，如果列表中有3個項目，並且每個項目需要1到4的值，則可以使用3位數字的3位數字。由於您的第一個數字是1，因此您將其分配給每個數字，並將其分配給列表項目。

在此，第一列是實際數量爲你計數，並且所述第二列被添加到每個數字用1相同的號碼，然後分配給每個三隻動物的值：

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-22 16:42:57

做一個範圍的係數組合？

回答

相關問題