CODEWITHSUNDEEP
pythonalgorithm
alkabary
alkabary

Reputation: 177

How to iterate over all these possibilities?

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 ?

Upvotes: 1

Views: 491

Answers (3)

Aguy
Aguy

Reputation: 8059

I don't know about execution efficiency, but for code writing efficiency you can consider:

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

Will only work for square list as in OP example.

Upvotes: 0

lcastillov
lcastillov

Reputation: 2153

This is a classic problem that can be solved using 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).

Upvotes: 8

Adam Smith
Adam Smith

Reputation: 54163

The naive implementation uses itertools.product to produce all possible pairings, then filters out the ones that won't work due to indexing issues.

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)

Upvotes: 0

Related Questions