私を助けてください！分割総額がお互いに近いところで分割を見つけたいですか？

Question

私がリストを持っているが

テスト= [10,20,30,40,50,60,70,80,90,100]

であると私はどこの分割を見つけたいです分割合計は、すべての可能な組み合わせであり、合計差が最小である分割を選択する分割数= 3によって互いに近接している。

例コードまたは単純なコードのPythonを入力してください。

は、この最初のスクリプトは、リストのすべての可能なトリプレットに入力リストを分割するために、二重forループを使用しています

非常K.ademarus

Answer 1

、ありがとうございました。各トリプレットについて、トリプレット内の各リストの合計を計算し、次にその合計の絶対差のdiffsというソート済みリストを作成します。 diffsとそれに続くトリプレットからなるタプルを、all_splitsというリストに保存します。最後に、all_splitsをソートし、all_splitsの各項目がdiffsで始まるため、保存されたタプルはdiffsの順にソートされます。

def split_list_test(lst): 
    all_splits = [] 
    for i in range(1, len(lst) - 1): 
     for j in range(i + 1, len(lst)): 
      splits = [lst[:i], lst[i:j], lst[j:]] 
      a, b, c = map(sum, splits) 
      diffs = sorted((abs(c-a), abs(c-b), abs(b-a)), reverse=True) 
      all_splits.append((diffs, splits)) 
    all_splits.sort() 
    return all_splits 

test = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] 

for row in split_list_test(test): 
    print(row) 

出力

([60, 40, 20], [[10, 20, 30, 40, 50], [60, 70, 80], [90, 100]]) 
([60, 40, 20], [[10, 20, 30, 40, 50, 60], [70, 80], [90, 100]]) 
([140, 110, 30], [[10, 20, 30, 40, 50, 60], [70, 80, 90], [100]]) 
([140, 120, 20], [[10, 20, 30, 40, 50], [60, 70], [80, 90, 100]]) 
([160, 90, 70], [[10, 20, 30, 40], [50, 60, 70, 80], [90, 100]]) 
([170, 90, 80], [[10, 20, 30, 40], [50, 60, 70], [80, 90, 100]]) 
([180, 110, 70], [[10, 20, 30, 40, 50, 60, 70], [80, 90], [100]]) 
([200, 110, 90], [[10, 20, 30, 40, 50, 60, 70], [80], [90, 100]]) 
([200, 140, 60], [[10, 20, 30, 40, 50, 60], [70], [80, 90, 100]]) 
([200, 150, 50], [[10, 20, 30, 40, 50], [60, 70, 80, 90], [100]]) 
([210, 160, 50], [[10, 20, 30], [40, 50, 60, 70], [80, 90, 100]]) 
([240, 130, 110], [[10, 20, 30], [40, 50, 60, 70, 80], [90, 100]]) 
([240, 220, 20], [[10, 20], [30, 40, 50, 60, 70], [80, 90, 100]]) 
([240, 230, 10], [[10, 20, 30, 40], [50, 60], [70, 80, 90, 100]]) 
([250, 250, 0], [[10, 20, 30, 40], [50, 60, 70, 80, 90], [100]]) 
([260, 260, 0], [[10], [20, 30, 40, 50, 60, 70], [80, 90, 100]]) 
([270, 260, 10], [[10, 20, 30, 40, 50, 60, 70, 80], [90], [100]]) 
([280, 190, 90], [[10, 20, 30], [40, 50, 60], [70, 80, 90, 100]]) 
([280, 190, 90], [[10, 20, 30, 40, 50], [60], [70, 80, 90, 100]]) 
([300, 160, 140], [[10, 20], [30, 40, 50, 60, 70, 80], [90, 100]]) 
([310, 160, 150], [[10, 20], [30, 40, 50, 60], [70, 80, 90, 100]]) 
([330, 190, 140], [[10], [20, 30, 40, 50, 60], [70, 80, 90, 100]]) 
([330, 290, 40], [[10, 20, 30], [40, 50, 60, 70, 80, 90], [100]]) 
([340, 180, 160], [[10], [20, 30, 40, 50, 60, 70, 80], [90, 100]]) 
([340, 310, 30], [[10, 20, 30], [40, 50], [60, 70, 80, 90, 100]]) 
([350, 300, 50], [[10, 20, 30, 40], [50], [60, 70, 80, 90, 100]]) 
([370, 280, 90], [[10, 20], [30, 40, 50], [60, 70, 80, 90, 100]]) 
([390, 260, 130], [[10], [20, 30, 40, 50], [60, 70, 80, 90, 100]]) 
([390, 320, 70], [[10, 20], [30, 40, 50, 60, 70, 80, 90], [100]]) 
([410, 390, 20], [[10, 20, 30], [40], [50, 60, 70, 80, 90, 100]]) 
([420, 380, 40], [[10, 20], [30, 40], [50, 60, 70, 80, 90, 100]]) 
([430, 340, 90], [[10], [20, 30, 40, 50, 60, 70, 80, 90], [100]]) 
([440, 360, 80], [[10], [20, 30, 40], [50, 60, 70, 80, 90, 100]]) 
([460, 460, 0], [[10, 20], [30], [40, 50, 60, 70, 80, 90, 100]]) 
([480, 440, 40], [[10], [20, 30], [40, 50, 60, 70, 80, 90, 100]]) 
([510, 500, 10], [[10], [20], [30, 40, 50, 60, 70, 80, 90, 100]]) 

---

次のスクリプトは、もう少しコンパクトであり、それは単一の解を返します。これは、最小の分割を決定するために別のルールを使用します。 (a, b, c)が最低から最高にソートされたトリプレットのリストの合計である場合、それらの合計の絶対差はc-a,c-b、およびb-aです。差の合計はc-a + c-b + b-aであり、これは2*(c-a)に等しいので、最小値がc-aのスプリットを探して、最小の分割（このルールを使用）を見つけることができます。

def keyfunc(seq): 
    sums = sorted(sum(u) for u in seq) 
    return sums[2] - sums[0] 

def split_list(lst): 
    gen = ([lst[:i], lst[i:j], lst[j:]] 
     for i in range(1, len(lst) - 1) 
      for j in range(i + 1, len(lst))) 
    return min(gen, key=keyfunc) 

test = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] 
print(split_list(test)) 

出力

[[10, 20, 30, 40, 50], [60, 70, 80], [90, 100]] 

あなたが見ることができるように、このtestリストについては、このバージョンでは、上記見つかった最小限の解決策の一つとして同じソリューションを提供します。