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

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

理由

假设我们有一个包含子数组的输入数组，如您的示例所示。每个子数组都有项目，其中是其索引，其键是 。我将第 th 个子数组的第 1 项称为 .$inputNCnn$inputKninVn,i

下面的算法可以通过归纳来证明是有效的（除了错误）：

1）对于N = 1，笛卡尔积只是 - C1项的总和。这可以通过一个简单的.array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... )foreach

2） 假设 已经持有第一个 N-1 子数组的笛卡尔积。和第 N 个子数组的笛卡尔积可以这样生成：$result$result

3）在每个项目（数组）里面，加上值。记住结果项目（具有附加值）;我将它称为.$productKN => VN,1$item

4a） 对于内部的每个数组：$product

4b） 对于集合中的每个值，添加到 的副本中，但将带有键的值更改为 （对于所有 ）。VN,2 ... VN,CN$product$itemKNVN,m2 <= m <= CN

两次迭代 4a（over）和 4b（在第 N 个输入子数组上）最终为迭代之前的每个项目都有项，因此最终确实包含前 N 个子数组的笛卡尔积。$product$resultCN$result

因此，该算法将适用于任何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