使用PHP关联数组查找笛卡尔积

使用PHP关联数组查找笛卡尔积

这是我不会感到羞耻的解决方案。

基本原理

像您的示例一样，假设我们有一个

$input

带有

N

子数组的输入数组。每个子数组都有

Cn

项目，其中

n

index在里面

$input

，键为

Kn

。我将把th子数组的

i

th项

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