用PHP关联数组寻找笛卡尔积
说我有一个如下的数组：
Array ( [arm] => Array ( [0] => A [1] => B [2] => C ) [gender] => Array ( [0] => Female [1] => Male ) [location] => Array ( [0] => Vancouver [1] => Calgary ) ) 我怎样才能find笛卡尔积，同时保留外关联数组的键，并在内部使用它们？ algorithm的结果应该是这样的：
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.
我查了很多笛卡尔乘积algorithm，但是我一直在关注如何保留关联关键字的细节。 我正在使用的当前algorithm只给出数字指标：
$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);
任何帮助，将不胜感激。
这是一个我不会感到羞愧的解决scheme。
合理
假设我们有一个包含N个子数组的input数组$input ，如你的例子。 每个子数组都有Cn项，其中n是$input索引，它的键是Kn 。 我将把第n个子arrays的第i项称为Vn,i 。
下面的algorithm可以通过归纳certificate是可行的（禁止错误）：
1）对于N = 1，笛卡尔乘积是简单的array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... ) 。 这可以用一个简单的foreach 。
2）假设$result已经保存了第一个N-1子arrays的笛卡尔乘积。 $result和第N个子数组的笛卡尔积可以这样产生：
3）在$product每个项目（数组）中，添加值KN => VN,1 。 记住结果项目（带有附加值）; 我将其称为$item 。
4a）对于$product每个数组：
4b）对于集合VN,2 ... VN,CN中的每个值，向$product添加一个$item的副本，但是用关键字KN将值更改为VN,m （对于所有2 <= m <= CN ）。
迭代4a（超过$product ）和4b（在第N个input子数组上）的两次迭代最终以$result ，每个迭代之前的项目都有CN项目，所以最终$result确实包含了笛卡尔乘积前N个子arrays。
因此，该algorithm将适用于任何N.
这本来比写得更难写。 我的正式certificate肯定是生锈的…
码
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));
看到它的行动！
这里是@ Jon的笛卡儿函数的优化版本：
function cartesian($input) { // filter out empty values $input = array_filter($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; }
这是algorithm背后的math： http : //en.wikipedia.org/wiki/Cartesian_product
以下是我可以想到的：
function inject($elem, $array) { return array_map(function ($n) use ($elem) { return array_merge((array)$elem, (array)$n); }, $array); } function zip($array1, $array2) { return array_reduce($array1, function ($v, $n) use ($array2) { return array_merge($v, inject($n, $array2)); }, array()); } function cartesian_product($array) { $keys = array_keys($array); $prod = array_shift($array); $prod = array_reduce($array, 'zip', $prod); return array_map(function ($n) use ($keys) { return array_combine($keys, $n); }, $prod); }
（使用下面的伪数组/列表/字典符号，因为PHP对于这样的事情来说太简单了。）
inject函数将a, [b]转换成[(a,b)] ，即它向数组的每个值注入单个值，返回数组数组。 无论a或b已经是数组，它总是会返回一个二维数组。
inject('a', ['foo', 'bar']) => [('a', 'foo'), ('b', 'bar')]
zip函数将inject函数应用于数组中的每个元素。
zip(['a', 'b'], ['foo', 'bar']) => [('a', 'foo'), ('a', 'bar'), ('b', 'foo'), ('b', 'bar')]
请注意，这实际上产生笛卡尔产品，所以zip是一个轻微的误用。 只需将这个函数连续应用于数据集中的所有元素，就可以为任意长度的数组提供笛卡尔积。
zip(zip(['a', 'b'], ['foo', 'bar']), ['42', '76']) => [('a', 'foo', '42'), ('a', 'foo', '76'), ('a', 'bar', '42'), …]
这不包含关键字，但是由于结果集中的元素都是按顺序排列的，因此您可以简单地将键重新注入结果中。
array_combine(['key1', 'key2', 'key3'], ['a', 'foo', '42']) => [ key1 : 'a', key2 : 'foo', key3 : '42' ]
将其应用于产品中的所有元素可以得到所需的结果。
如果你愿意的话，你可以把上面的三个函数合并成一个单独的long语句（这也可以清除不一致的错误）。
对于PHP <= 5.2，没有匿名函数的“展开”版本将如下所示：
function inject($elem, $array) { $elem = (array)$elem; foreach ($array as &$a) { $a = array_merge($elem, (array)$a); } return $array; } function zip($array1, $array2) { $prod = array(); foreach ($array1 as $a) { $prod = array_merge($prod, inject($a, $array2)); } return $prod; } function cartesian_product($array) { $keys = array_keys($array); $prod = array_shift($array); $prod = array_reduce($array, 'zip', $prod); foreach ($prod as &$a) { $a = array_combine($keys, $a); } return $prod; }
为什么不使用recursion生成器…内存问题：接近无
（而且很漂亮）
function cartesian($a) { if ($a) { if($u=array_pop($a)) foreach(cartesian($a)as$p) foreach($u as$v) yield $p+[count($p)=>$v]; } else yield[]; }
注意：这不保留键; 但这是一个开始。
这应该做（未testing）：
function acartesian($a) { if ($a) { $k=end(array_keys($a)); if($u=array_pop($a)) foreach(acartesian($a)as$p) foreach($u as$v) yield $p+[$k=>$v]; } else yield[]; }
我很快调整了一下你的代码，我的想法很粗鲁，但是看看这个工作是否正常：
$result = array(); $nm = ''; foreach ($map as $name => $a) { if (empty($result)) { $result = $a; $nm = $name; continue; } $res = array(); foreach ($result as $r) { foreach ($a as $v) { $myr = $r; $myv = $v; if(!is_array($r)) $myr = array($nm => $r); if(!is_array($v)) $myv = array($name => $v); $res[] = array_merge($myr, $myv); } } $result = $res; } echo "<pre>"; print_r($result);
另一个scheme
function getAllVariations($input) { $result = array(); $cnt = array_product(array_map('count', $input)); $step = 1; foreach ($input as $key=>$array) { for ($i=0; $i<$cnt; $i++) { foreach ($array as $value) { for ($k=0; $k<$step; $k++) { $result[$i+$k][$key] = $value; } $i += $step; } $i--; } $step = $step * count($array); } return $result; }
用法：
$input = array( 'arm' => array('A', 'B', 'C'), 'gender' => array('Female', 'Male'), 'location' => array('Vancouver', 'Calgary'), 'name' => array('Rio', 'Mark') ); echo "<pre>"; var_dump(getAllVariations($input));
为什么不使用数据库来做到这一点？
在MySQL中很容易
table arm id integer primary key label char table gender id integer primary key gender enum('male','female') table location id integer primary key city varchar(255)
然后做一个查询
$query = mysql_query(" SELECT a.label, g.gender, l.city FROM arm a CROSS JOIN gender g CROSS JOIN location l ORDER BY a.id ") or die("Could not execute query"); while($row = mysql_fetch_array($query) ) { .... }
并读出来：
如果内存消耗很重要，或者最终不需要所有组合，则可以使用迭代器一次生成一个组合。 如果你需要所有的组合，你可以使用iterator_to_array 。
function cartezianIterator($inputArray) { $maximumPosition = array_map('count', $inputArray); $position = array_pad([], count($inputArray), 0); while (false !== ($item = buildItemAtPosition($inputArray, $position))) { yield $item; $position = incrementPosition($position, $maximumPosition); } } function buildItemAtPosition($inputArray, $positions) { if ($positions[0] >= count($inputArray[0])) { return false; } $item = []; foreach ($inputArray as $rowIndex => $row) { $position = $positions[$rowIndex]; $item[] = $row[$position]; } return $item; } function incrementPosition($position, $maximumPosition) { $digitToIncrement = count($position) - 1; do { $position[$digitToIncrement]++; if ($position[$digitToIncrement] < $maximumPosition[$digitToIncrement] || 0 === $digitToIncrement) { //no overflow break; } //overflow, reset to zero and increment parent digit $position[$digitToIncrement] = 0; $digitToIncrement--; } while ($digitToIncrement >= 0); return $position; }
然后，要一次获得一个解决scheme，可以使用foreach或next ，如下所示：
$iterator = cartezianIterator($inputArray); //of course, you need to do something with the result... $combination = next($iterator); $combination = next($iterator); $combination = next($iterator); $combination = next($iterator); $combination = next($iterator); $combination = next($iterator);
如果你只需要几个组合，这个解决scheme非常快。 此外，内存消耗非常低（它使用平坦的array来存储一些integers ）。
注意：不使用recursion函数。
一种algorithm是在每一步中扩展以前的结果与当前的步骤项目：
function cartezian1($inputArray) { $results = []; foreach ($inputArray as $group) { $results = expandItems($results, $group); } return $results; } function expandItems($sourceItems, $tails) { $result = []; if (empty($sourceItems)) { foreach ($tails as $tail) { $result[] = [$tail]; } return $result; } foreach ($sourceItems as $sourceItem) { foreach ($tails as $tail) { $result[] = array_merge($sourceItem, [$tail]); } } return $result; }
此解决scheme使用内存来存储所有组合，然后一次返回全部组合。 所以它速度很快，但需要大量的内存。 而且，不使用recursion函数。
在PHP 7中@Serg的答案可以缩短为：
function cartesian(array $input) { $result = [[]]; foreach ($input as $key => $values) { $append = []; foreach ($values as $value) { foreach ($result as $data) { $append[] = $data + [$key => $value]; } } $result = $append; } return $result; }
