和の値が小さくなる集合からサイズrの組み合わせを見つける

Question

数字のセットがある。 [100,90,80,70,60,50]と、サイズがr=3のすべての組み合わせを検索したいが、合計が減少する順に表示する。 数値を降順に並べ替えるなどの機能はありません。

(100, 90, 80) 270 
(100, 90, 70) 260 
(100, 90, 60) 250 
(100, 90, 50) **240** 
(100, 80, 70) **250** 
(100, 80, 60) 240 

このような組み合わせを減らすことで、どのように組み合わせを見つけることができますか。

Answer 1

最初の（そして素朴な）解決策は、すべての可能性のある順列に対して反復し、それらのセットを最小ヒープに保存することです。最後にすべてのセットを1つずつ削除してください。
実行時間：今* を
あなたがそれまでは判明最小数を保存する必要があります*今
：秒1は少し複雑です

（xlogx）Oので、Rを選択し、X = Nと仮定1つの変更であなたのサンプルとまったく同じように繰り返します。次に移動するセットが何であるかを知るには、現在のセットのすべての番号を配列の次の番号に置き換え、最小のものよりも小さいあなたは貯蓄しています。もちろん最小値を新しい最小値に設定します。
実行時間：ここではO（（N Rを選択してください）* R）

Answer 2

は、」上記のコードのためのコード

import itertools 

array = [100,90,80,70,60,50] 
size = 3 
answer = [] # to store all combination 
order = [] # to store order according to sum 
number = 0 # index of combination 

for comb in itertools.combinations(array,size): 
    answer.append(comb) 
    order.append([sum(comb),number]) # Storing sum and index 
    number += 1 

order.sort(reverse=True) # sorting in decreasing order 

for key in order: 
    print key[0],answer[key[1]] # key[0] is sum of combination 

出力は

270 (100, 90, 80) 
260 (100, 90, 70) 
250 (100, 80, 70) 
250 (100, 90, 60) 
240 (90, 80, 70) 
240 (100, 80, 60) 
240 (100, 90, 50) 
230 (90, 80, 60) 
230 (100, 70, 60) 
230 (100, 80, 50) 
220 (90, 70, 60) 
220 (90, 80, 50) 
220 (100, 70, 50) 
210 (80, 70, 60) 
210 (90, 70, 50) 
210 (100, 60, 50) 
200 (80, 70, 50) 
200 (90, 60, 50) 
190 (80, 60, 50) 
180 (70, 60, 50)