これらのすべての可能性をどのように反復するのですか？

Question

私は、次のよう

合計を合計値を定義し、我々はPythonのリスト

list = [[1,2,3],[4,5,6],[7,8,9]] 

があるとします。サブリストのそれぞれから単一のエントリ（異なるインデックス）の総和があります。

これは、私は例を与える複雑な音上記リストは

1は、第1のサブリストからであり、5秒のサブリストからのものであり、9であるため、1 + 5 + 9の合計の一つであります3番目のサブリストからは、それぞれ対応するサブリスト内の位置が異なります。

だから、私は1 + 4 + 7を持つことができません。その理由は、1,4 &がサブリストの最初のエントリであるからです。

、両方例えば自分のリストにあるので、

上の第二エントリで と私はそれぞれの個々のエントリの合計の最高の合計を見つけたい5 & 8ので、私は1 + 5 + 8を持つことができません

サブリスト!!

これらのすべての可能な合計をどのように反復し、これらの合計のうち最高のものを得ることができますか。

上記のリストについては、3^3 = 27個の異なる合計があります。

そして、pythonで効率的な方法がありますか？

Answer 1

これは、Hungarian algorithmを使用して解決できる古典的な問題です。

from sklearn.utils.linear_assignment_ import linear_assignment 
import numpy as np 

M = [[1,2,3],[4,5,6],[7,8,9]] 

M = np.array(M) #convert to numpy array 

result = linear_assignment(M) 

answer = sum(M[cell[0]][cell[1]] for cell in result) 

すべての可能な和を反復することは悪い考えです（O（N！））。上記のアルゴリズムはO（N^3）で実行する必要があります。

Answer 2

純粋な実装では、itertools.productを使用してすべての可能なペアリングを生成し、インデックスの問題のために機能しないペアを除外します。

from itertools import product 

lst = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 

with_indices = [ [(idx, val) for idx, val in enumerate(sublst)] for sublst in lst] 
# [ [(0, 1), (1, 2), (2, 3)], 
# [(0, 4), (1, 5), (2, 6)], 
# [(0, 7), (1, 8), (2, 9)] ] 

total_product = product(*with_indices) 

filtered_product = [ 
    [p[0][1], p[1][1], p[2][1]] for p in total_product if 
     len(set([p[0][0], p[1][0], p[2][0]])) == 3] 
# p[0][1], p[1][1], p[2][1] refers to original values 
# p[0][0], p[1][0], p[2][0] refers to original indices 
# asserting the length of the set of indices is 3 ensures that all are unique. 

# [[1, 5, 9], 
# [1, 6, 8], 
# [2, 4, 9], 
# [2, 6, 7], 
# [3, 4, 8], 
# [3, 5, 7]] 

result = max(filtered_product, key=sum) 

Answer 3

私は約実行効率を知りませんが、コードの書き込み効率のためにあなたが考えることができます。

for k in itertools.permutations(lst): 
    print(sum([j[i] for i, j in enumerate(k)])) 

はOPの例のように正方形のリストのために動作します。