How to find the minimal sum of numbers drawn from multiple arrays?

Question

I was wondering what would be the best way to go about solving the following problem. I was writing this in PHP but it is more of a general programming problem and I guess it involves search algorithms and combinatorics.

Given an array containing multiple arrays/sets of numbers

$a[0] = array(1,2,3,4,5);
$a[1] = array(1,3,5,7,9);
$a[2] = array(2,4,6,8,10);

I would like to draw a number from each array such that the sum of the drawn numbers is the smallest possible. Also the number must be drawn from a unique array index, so in this example you couldn't draw 1, 1, 2. The smallest possible number sequence from the arrays above would be 3, 1, 4 which would give a sum of 8.

Now assume an input array of n arrays/sets containing each m numbers, what would be the most logical and efficient way to find the optimal sequence of numbers?

It's not homework, I encountered the problem in creating an application. My solution consisted of `n` for loops nested in each other along with a variable to keep track of the minimal sum. It did work but turned out to be very ugly code, so I was just wondering what the right approach would be here. My guess is that it would best be solved recursively, but I thought it wouldn't hurt to ask for input from other programmers. — dljve, Mar 13 '14 at 14:39
Use the min() function. Then remove anything lower than current result from next array. Repeat for next array. Not really a recursive problem as your arrays arent recursive. — ToBe, Mar 13 '14 at 14:48
ToBe, I don't think that would work. If I would start with the first array (in the example) and use the min() function it would return 1, and for the next arrays it would return 3 and 6. The sum of those values would be 10 which isn't minimal in this case. — dljve, Mar 13 '14 at 14:57

score 1 · Accepted Answer · edited May 23 '17 at 12:27

Assuming all arrays are sorted, we can ignore the elements at indexes >= n (so we can focus on the square matrix n * n)
We generate all permutations recursively as in Permutations - all possible sets of numbers and for each permutation we count the sum. Though it is not optimal, but it is better than n nested for loops:

$minSum = PHP_INT_MAX;

$a[0] = array(1,2,3,4,5);
$a[1] = array(1,3,5,7,9);
$a[2] = array(2,4,6,8,10);

function pc_permute($items, $perms = array( )) {
    global $a, $minSum;
    if (empty($items)) {
        $sum = 0;
        foreach($perms as $i => $p) {
          $sum += $a[$i][$p];
        }
        if($sum<$minSum) {
          $minSum = $sum;
        }
    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

pc_permute(range(0,count($a)-1));

echo "$minSum\n";

Using a function to generate the permutations of the indices and then calculating the sum for each of those seems like a very good approach. I didn't think of it myself in time, thank you! — dljve, Mar 13 '14 at 15:24

How to find the minimal sum of numbers drawn from multiple arrays?

1 Answers1