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?

Answer 1

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";