Lot*_*tes 48 php algorithm associative-array cartesian-product
假设我有一个如下所示的数组:
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);
任何帮助,将不胜感激.
Jon*_*Jon 55
这是一个我不会感到羞耻的解决方案.
假设我们有一个$input带有N子数组的输入数组,如您的示例所示.每个子数组都有Cn项,n其索引位于其中$input,其关键是Kn.我将涉及i所述的个项n个子阵列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));
Ser*_*nko 40
这是@ 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
在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 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[];
}