Match indexes from 1 to n with n given arrays so that sum of elements is minimal

Question

Originally I faced a problem: I had three arrays of the same length (say, a, b, c), and I needed to choose indexes i, j, k distinct from each other that the sum a_i + b_j + c_k would be minimal. I deduced that only the least three elements of each array can be included in the sum in order for it to be minimal. For example, if we have two arrays a, b of two elements the thing is simple.

1. Find the minimum of a, the minimum of b
2. If they are on different positions, it's good. If not, we compare a_next - a_min < b_next - b_min. If it's true, we take b_min and a_next. If not, we take a_min and b_next.

I cannot work out the algorithm for three arrays of three numbers each because the index conflicts may overlap an example:

 8 1 3 => a
19 1 6 => b
18 2 1 => c

I want to take a_2,b_2,c_3 (1-based), but I cannot. I move a pointer to 3rd because 3-1 < 6-1. But now there's a conflict with c, so I've got to move it to the 2nd (2-1 < 3-8). But the second is already occupied with b, so I move c to the 1st (18-2 < 19-1).

The result is a_3 + b_2 + c_1, which is wrong because c_2 + a_1 + b_3 would be less (22 > 11).

Also we should consider situations when all a_min, b_min, c_min are at the same position.

I think I'm stuck.

The problem with three arrays of three elements is solved quite easily by bruteforce (3! possible cases), but I feel like O(n!) is really ineffective if we start talking f.e. about 1000 arrays. I think that double pointer is the key to solve it but can't get my head around it.

Answer 1

This is an integer linear programming problem. https://en.wikipedia.org/wiki/Integer_programming

Let v_a_i be the value of selecting the ith member of the ath array

Let

n(array_index, element index ) = ( array index ) * array_count + (element index)

xn = 1 if n(array_index, element index ) selected, otherwise 0.

You want to minimize sum xn * v_a_i for all a and i

For your example

MIN Z = 8x1 + x2 + 3x3 + 19x4 + x5 + 6x6 + 18x7 + 2x8 + x9

subject to

( ensures that all indices are different )
x1 + x4 + x7 = 1
x2 + x5 + x8 = 1
x3 + x6 + x9 = 1

( ensures that only one selection from each array )
x1 + x2 + x3 = 1
x4 + x5 + x6 = 1
x7 + x8 + x9 = 1

and x1,x2,x3,x4,x5,x6,x7,x8,x9 >= 0



Find solution using 0-1 Integer programming problem method
MIN Z = 8x1 + x2 + 3x3 + 19x4 + x5 + 6x6 + 18x7 + 2x8 + x9
subject to
x1 + x4 + x7 = 1
x2 + x5 + x8 = 1
x3 + x6 + x9 = 1
x1 + x2 + x3 = 1
x4 + x5 + x6 = 1
x7 + x8 + x9 = 1
and x1,x2,x3,x4,x5,x6,x7,x8,x9 >= 0


Solution is
Min ZA=10 (x1=1,x2=0,x3=0,x4=0,x5=1,x6=0,x7=0,x8=0,x9=1)