Friday, May 13, 2011

generate combinations of elements from multiple arrays

Problem: we have multiple arrays, and we must find all combinations of the elements of these arrays. For example, if we have two array:

$option1 = array('apple', 'orange', 'pear');
$option2 = array('rice', 'noodle');

And we must find all combinations(there are 6 of them in this example) of these two array elements:

'apple', 'rice',
'apple', 'noodle',
'orange', 'rice',
'orange', 'noodle',
'pear', 'rice',
'pear', 'noodle'

First, let's see how to implement the algorithm in PHP:

//$allOptionsArray is an array containing all options array
//$final is a stdClass
function getCombinations($allOptionsArray, $final) {
    if(count($allOptionsArray)) {
        for($i=0; $i < count($allOptionsArray[0]); $i++) {
            $tmp = $allOptionsArray;
            $final->codes[$final->pos] = $allOptionsArray[0][$i];
            array_shift($tmp);
            $final->pos++;
            getCombinations($tmp, $final);
        }
    } else {
        $final->result[] = $final->codes;
    }
    $final->pos--;
}
//let's see how to use the function:
$option1 = array('apple', 'orange', 'pear');
$option2 = array('rice', 'noodle');
$allOptionsArray = array($option1, $option2);
$final = new stdClass();
$final->result = array();
$final->codes  = array();
$final->pos    = 0;
getCombinations($allOptionsArray, $final);
//$final->result is an array containing all possible combinations
var_dump($final->result);

We can easily implement same algorithm in javascript:

var getCombinations = function(allOptionsArray, combination) {
    if(allOptionsArray.length > 0) {
        for(var i=0; i < allOptionsArray[0].length; i++) {
            var tmp = allOptionsArray.slice(0);
            combination.codes[combination.counter] = allOptionsArray[0][i];
            tmp.shift();
            combination.counter++;
            getCombinations(tmp, combination);
        }
    } else {
        var combi = combination.codes.slice(0);
        combination.result.push(combi);
    }
    combination.counter--;
}

//use it:
var a = ["01", "02", "03", "04"];
var b = ["white", "green", "blue", "red"];
var c = ["one", "two", "three", "four"];
var d = ["a", "b", "c", "d"];

var allOptionsArray = [a, b, c, d];
var combination = {codes : [], result : [], counter : 0};

getCombinations(allOptionsArray, combination);

for(var i=0; i < combination.result.length; i++) {
    console.log(combination.result[i]);
}

5 comments:

Murali said...

thanks

Miguel web online said...

With this code you can print the combinations between two arrays in one way,

";
}
echo "
";
}


?>

Result:

Play in the park
Walk in the park

Play on the beach
Walk on the beach

Matt Butler said...

This helped me out a bunch. Thanks!

Anonymous said...

Great job!!!

Alwin Co Daan said...

Great & Useful Blog. Helped me a lot.
PHP Training in Chennai
PHP Online Training India