python - 如何遍历所有这些可能性？

Question

假设我们有一个 python 列表

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

我定义总和如下，

sum:是每个子列表中单个条目(不同索引)的总和。

这听起来很复杂，所以我举个例子，

对于上面的列表，1 + 5 + 9 是其中一个和，因为 1 来自第一个子列表，5 来自第二个子列表，9 来自第三个子列表，它们在相应子列表中的位置不同。

所以我不能有 1 + 4 + 7 因为 1,4 & 7 是它们子列表中的第一个条目。

我不能有 1 + 5 + 8 因为 5 和 8 都是它们列表中的第二个条目，依此类推

例如，我想找到每个子列表的单个条目总数的最高总和!!

我如何遍历所有这些可能的总和，然后从所有这些总和中获得最高值。

对于上面的列表，我们有 3^3=27 个不同的和。

有没有一种使用 python 的有效方法？

Answer 1

这是一个可以使用 Hungarian algorithm 解决的经典问题. sklearn中有一个实现:

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) 内运行。