Finding cartesian product with PHP associative arrays

Question

Say that I have an array like the following:

Array (     [arm] => Array         (             [0] => A             [1] => B             [2] => C         )     [gender] => Array         (             [0] => Female             [1] => Male         )     [location] => Array         (             [0] => Vancouver             [1] => Calgary         ) ) 

How can I find the cartesian product while preserving the keys of the outer associative array and using them in the inner ones? The result of the algorithm should be this:

Array (     [0] => Array         (             [arm] => A             [gender] => Female             [location] => Vancouver         )      [1] => Array         (             [arm] => A             [gender] => Female             [location] => Calgary         )      [2] => Array         (             [arm] => A             [gender] => Male             [location] => Vancouver         )  ...etc. 

I've looked up quite a number of cartesian product algorithms but I'm getting stuck on the specifics of how to preserve the associative keys. The current algorithm I am using gives numerical indices only:

    $result = array();     foreach ($map as $a) {         if (empty($result)) {             $result = $a;             continue;         }         $res = array();         foreach ($result as $r) {             foreach ($a as $v) {                 $res[] = array_merge((array)$r, (array)$v);             }         }         $result = $res;     }      print_r($result); 

Any help would be appreciated.

Answer 1

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 ith item of the nth 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)); 

Answer 2

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