Finding cartesian product with PHP associative arrays
Here's a solution I wouldn't be ashamed to show.
Rationale
Assume that we have an input array $input
with N
sub-arrays, as in your example. Each sub-array has Cn
items, where n
is its index inside $input
, and its key is Kn
. I will refer to the i
th item of the n
th sub-array as Vn,i
.
The algorithm below can be proved to work (barring bugs) by induction:
1) For N = 1, the cartesian product is simply array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... )
-- C1 items in total. This can be done with a simple foreach
.
2) Assume that $result
already holds the cartesian product of the first N-1 sub-arrays. The cartesian product of $result
and the Nth sub-array can be produced this way:
3) In each item (array) inside $product
, add the value KN => VN,1
. Remember the resulting item (with the added value); I 'll refer to it as $item
.
4a) For each array inside $product
:
4b) For each value in the set VN,2 ... VN,CN
, add to $product
a copy of $item
, but change the value with the key KN
to VN,m
(for all 2 <= m <= CN
).
The two iterations 4a (over $product
) and 4b (over the Nth input sub-array) ends up with $result
having CN
items for every item it had before the iterations, so in the end $result
indeed contains the cartesian product of the first N sub arrays.
Therefore the algorithm will work for any N.
This was harder to write than it should have been. My formal proofs are definitely getting rusty...
Code
function cartesian($input) { $result = array(); while (list($key, $values) = each($input)) { // If a sub-array is empty, it doesn't affect the cartesian product if (empty($values)) { continue; } // Seeding the product array with the values from the first sub-array if (empty($result)) { foreach($values as $value) { $result[] = array($key => $value); } } else { // Second and subsequent input sub-arrays work like this: // 1. In each existing array inside $product, add an item with // key == $key and value == first item in input sub-array // 2. Then, for each remaining item in current input sub-array, // add a copy of each existing array inside $product with // key == $key and value == first item of input sub-array // Store all items to be added to $product here; adding them // inside the foreach will result in an infinite loop $append = array(); foreach($result as &$product) { // Do step 1 above. array_shift is not the most efficient, but // it allows us to iterate over the rest of the items with a // simple foreach, making the code short and easy to read. $product[$key] = array_shift($values); // $product is by reference (that's why the key we added above // will appear in the end result), so make a copy of it here $copy = $product; // Do step 2 above. foreach($values as $item) { $copy[$key] = $item; $append[] = $copy; } // Undo the side effecst of array_shift array_unshift($values, $product[$key]); } // Out of the foreach, we can add to $results now $result = array_merge($result, $append); } } return $result;}
Usage
$input = array( 'arm' => array('A', 'B', 'C'), 'gender' => array('Female', 'Male'), 'location' => array('Vancouver', 'Calgary'),);print_r(cartesian($input));
Here is optimized version of @Jon's cartesian function:
function cartesian($input) { $result = array(array()); foreach ($input as $key => $values) { $append = array(); foreach($result as $product) { foreach($values as $item) { $product[$key] = $item; $append[] = $product; } } $result = $append; } return $result;}
Read more about the math behind this algorithm: http://en.wikipedia.org/wiki/Cartesian_product
See more examples of this algorithm in different languages: https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists
In PHP 7 @Serg's answer can be shortened to:
function cartesian(array $input){ $result = [[]]; foreach ($input as $key => $values) { $append = []; foreach ($values as $value) { foreach ($result as $data) { $append[] = $data + [$key => $value]; } } $result = $append; } return $result;}