How to iterate over all these possibilities?
Question: Assume we have a python list

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

I define the sum as the following,

sum: is the total sum of single entries (different index) from each of the
sublists.

This sounds complex so I will give an example,

for the above list, 1 + 5 + 9 is one of the sums because 1 is from the first
sublist and 5 is from the second sublist and 9 is from the 3rd sublist and
they all have different positions in their corresponding sublist.

so i can't have `1 + 4 + 7` because 1,4 & 7 are first entries in their
sublists.

I can't have `1 + 5 + 8` because 5 & 8 are both second entries in their list
and so on

for example, and I want to find the highest sum of the total of individual
entries of each of the sublist !!

How can I iterate over all these possible sums and then get the highest out of
all these sums.

For the above list, we have 3^3=27 different sums.

And is there an efficient way to do it with python ?


Answer: This is a classic problem that can be solved using [Hungarian
algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm). There is an
implementation in 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)
    

Iterate over all possible sums is a bad idea (O(N!)). The algorithm above must
run in O(N^3).

