假设我有一个如下所示的数组：
Array
(
[arm] => Array
(
[0] => A
[1] => B
[2] => C
)
[gender] => Array
(
[0] => Female
[1] => Male
)
[location] => Array
(
[0] => Vancouver
[1] => Calgary
)
)
如何在保留外部关联数组的键并在内部关联数组中使用它们的同时找到笛卡尔积？算法的结果应该是这样的：
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.
我已经查找了相当多的笛卡尔乘积算法，但我被困在如何保留关联键的细节上。我正在使用的当前算法仅给出数字索引：
$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);
任何帮助将不胜感激。
这是一个我不会羞于展示的解决方案。
理由
假设我们有一个包含N子数组的输入数组$input，如您的示例所示。每子数组有 Cn 项，其中 n 是它在 $input 中的索引，它的键是 Kn 。我将第 n 个子数组的第 i 项称为 Vn,i 。
下面的算法可以通过归纳法证明是有效的(除非有错误(：
1( 对于 N = 1，笛卡尔积只是 array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... ) -- 总共 C1 项。这可以通过一个简单的foreach来完成。
2( 假设$result已经持有前 N-1 个子数组的笛卡尔乘积。$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 个输入子数组(最终导致 $result 在迭代之前的每个项目都有 CN 个项目，所以最终$result确实包含前 N 个子数组的笛卡尔乘积。
因此，该算法将适用于任何 N。
这比它应该写的更难写。我的正式证明肯定生锈了...
法典
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) {
$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;
}
阅读更多关于此算法背后的数学：http://en.wikipedia.org/wiki/Cartesian_product
查看不同语言的此算法的更多示例：https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists
为什么不使用递归生成器...内存问题：几乎无
(而且很漂亮(
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[];
}
注意：这不会保留密钥;但这是一个开始。
这应该做(未测试(：
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[];
}
在 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;
}
这是我能想到的：
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' ]
将其应用于产品中的所有元素可产生所需的结果。
如果您愿意，您可以将上述三个函数折叠成一个长语句(这也将清除用词不当(。
对于 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;
}
另一种解决方案：
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));
如果内存消耗很重要，或者您最终不需要所有组合，则可以使用迭代器一次生成一个组合。如果您需要所有组合，您可以使用 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;
}
然后，要一次获得一个解决方案，您可以使用 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);
如果您只需要几个组合，此解决方案非常非常快。此外，内存消耗非常低(它使用扁平array来存储一些integers(。
注意：不使用递归函数。
我快速调整了一下您的代码，我认为我的尝试很粗糙，但看看这是否如您所愿：
$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);
为什么不使用数据库来执行此操作？
这在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) )
{
....
}
并读出：
一种算法是在每个步骤中扩展当前步骤项的先前结果：
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;
}
此解决方案使用内存来存储所有组合，然后一次返回所有组合。所以，它很快，但它需要大量内存。此外，不使用递归函数。