Lotus Notes - 3 months ago 12

PHP 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

Here's a solution I wouldn't be ashamed to show.

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

```
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;
}
```

```
$input = array(
'arm' => array('A', 'B', 'C'),
'gender' => array('Female', 'Male'),
'location' => array('Vancouver', 'Calgary'),
);
print_r(cartesian($input));
```