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.

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

## Usage