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