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

Question

假设我有一个如下数组:

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

任何帮助将不胜感激。

Answer 1

这是一个我不会羞于展示的解决方案。

基本原理

假设我们有一个输入数组 $input与 N子数组，如您的示例中所示。每个子数组有 Cn项目，其中 n是它在 $input 内的索引吗？ ，它的键是Kn .我会引用 i n 的第一项th 子数组为 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));