Finding cartesian product with PHP associative arrays

algorithm, associative-array, cartesian-product, php

Solution

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:

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`.

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:

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.

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

Problem

Original source

Related problems

• Concatenate values of n arrays in php