列表中所有可能的金額，每個列表只能彙總一個條目

Question

我正在Python中製作一個練習程序，用一組給定的板子計算我可以放在機架上的所有不同重量。

def Weights(t=1,f=1,tn=1,tf=1,thf=1,ff=1,b=45): 

    Max=b+5*t+10*f+20*tn+50*tf+70*thf+90*ff 
    Poss=range(b,Max+1,5) 

    ts=(list((i*5 for i in range(0,t+1)))) 
    fs=(list((i*10 for i in range(0,f+1)))) 
    tns=(list((i*20 for i in range(0,tn+1)))) 
    tfs=(list((i*50 for i in range(0,tf+1)))) 
    thfs=(list((i*70 for i in range(0,thf+1)))) 
    ffs=(list((i*90 for i in range(0,ff+1)))) 

Weights() 

這給我留下了6個列表。爲了獲得所有的組合，我需要將列表中的一個元素與每個其他列表中的一個元素相加。在這一點上，這顯然是一個線性代數問題，我只是不知道如何在Python中表達這一點，特別是因爲我不想使用插件（No NumPy）

Answer 1

迭代要獲得所有的連擊，我需要將列表中的一個元素與每個其他列表中的一個元素相加。

聽起來像是你想itertools.product。爲了簡化的例子，讓我們只需要三年的七個項目中（但它的瑣碎傳遞更多或更少，參數爲product）：

import itertools 

b = [45] # I assume this represents the "bar" and that it's not optional 
ts = [0, 5, 10, 15] 
fs = [0, 10] 

combos = itertools.product(b, ts, fs) 
for combo in combos: print(list(combo)) 

打印以下內容：

[45, 0, 0] 
[45, 0, 10] 
[45, 5, 0] 
[45, 5, 10] 
[45, 10, 0] 
[45, 10, 10] 
[45, 15, 0] 
[45, 15, 10] 

...這聽起來像你想要的時候你所說的「所有組合」。

要獲得每個的總和，它都可以在一個行來完成：

totals = [sum(combo) for combo in itertools.product(b, ts, fs)] 

下面是參數化功能的一個可能的靈活的方式：

import itertools 

def PossibleWeights(*weights): 
    return list(itertools.product(*[[weightset] if isinstance(weightset, (int, float)) else [sum(weightset[:i]) for i in range(len(weightset)+1)] for weightset in weights])) 

你打電話時，說， PossibleWeights(45, [10]*2, [5]*3)該調用本身使其明確（可讀），即有一個強制性的45磅重，兩個可能的10磅重和三個可能的5磅重。對於您傳遞了多少個這樣的參數以及它們的值是什麼，您擁有完全的靈活性。

然後，您可以使用dict每個總重量來實現它（順便說一句刪除重複的總數，有超過一個的組合加起來相同的總）組合關聯：

d = {} 
for combo in PossibleWeights(45, [10]*2, [5]*3): 
    d[sum(combo)] = combo 

.. 。而再漂亮，打印結果：

for total, combo in sorted(d.items()): 
    print('sum(%r) = %r' % (combo, total)) 

輸出：

sum((45, 0, 0)) = 45 
sum((45, 0, 5)) = 50 
sum((45, 10, 0)) = 55 
sum((45, 10, 5)) = 60 
sum((45, 20, 0)) = 65 
sum((45, 20, 5)) = 70 
sum((45, 20, 10)) = 75 
sum((45, 20, 15)) = 80 

順便說一句：如果你想要使用最少數量的印版達到每個印版總數，請確保在打電話給PossibleWeights時，在較輕的印版之前通過較重的印版，如上例所示。

平衡杆的兩側作爲練習留給讀者;-)

Answer 2

我認爲你的方法是錯誤的，也是你的簽名是不好的設計：如果你有7種以上不同的重量？我認爲輸入爲元組列表（weight，max_number）更合適。當你開始用這些術語思考時，你明白「交叉連接」7列表也是錯誤的方法。你想要的是有一個所有簡單權重的列表，而不是得到power set即所有子集。 Rosetta Code在Python中有幾個很好的功能集。我特別喜歡這一個，因爲它不強制代全功率設置在內存中，這可能是一個問題：

def powersequence(val): 
    ''' Generate a 'powerset' for sequence types that are indexable by integers. 
     Uses a binary count to enumerate the members and returns a list 

     Examples: 
      >>> powersequence('STR') # String 
      ['', 'S', 'T', 'ST', 'R', 'SR', 'TR', 'STR'] 
      >>> powersequence([0,1,2]) # List 
      [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]] 
      >>> powersequence((3,4,5)) # Tuple 
      [(), (3,), (4,), (3, 4), (5,), (3, 5), (4, 5), (3, 4, 5)] 
      >>> 
    ''' 
    vtype = type(val); vlen = len(val); vrange = range(vlen) 
    return [ reduce(lambda x,y: x+y, (val[i:i+1] for i in vrange if 2**i & n), vtype()) 
      for n in range(2**vlen) ] 

，也可以使用itertools powerset recipe這是在實踐中更快（感謝umutto）

一個建

def powersequence(val): 
    s = list(iterable) 
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 

所以算法是：簡單的權重

1. 生成單獨的列表（加入您的ts，fs，...的）
2. 使用powersequence產生冪
3. 總和每個子集
4. 推結果所有項目設置來篩選唯一

def all_weights(ws): 
    simpleWeights = [0] # add 0 just one time 
    for (w, c) in ws: 
     simpleWeights = simpleWeights + [w] * c 
    allWeights = (sum(subset) for subset in powersequence(simpleWeights)) 
    return set(allWeights) # filter uniqueness 


all = all_weights([(1, 1), (5, 1), (10, 1), (20, 1), (50, 1), (70, 1), (90, 1)]) 
for w in all: 
    print(w) 

注意，整個收集到內存中的唯一條件力量物化所以這可能是這個代碼可以解決的問題的一個限制因素。

更新

其實傑斯是正確的：做的金幣表的產品將是顯著更快然後通過加入列表

的 powersequence

def all_weights(ws): 
    simpleWeights = [] 
    for (w, c) in ws: 
     simpleWeights.append(list((i * w for i in range(0, c + 1)))) 

    allWeights = (sum(subset) for subset in itertools.product(*simpleWeights)) # note "*" before simpleWeights! 
    return set(allWeights) # filter uniqueness