查找乘积PHP关联数组 [英] Finding cartesian product with PHP associative arrays

问题描述

有人说我像下面的数组：

Say that I have an array like the following:

Array
(
    [arm] => Array
        (
            [0] => A
            [1] => B
            [2] => C
        )
    [gender] => Array
        (
            [0] => Female
            [1] => Male
        )
    [location] => Array
        (
            [0] => Vancouver
            [1] => Calgary
        )
)

我如何才能找到，而preserving外关联数组的键，并使用他们在内部的笛卡尔积？该算法的结果应该是这样的：

How can I find the cartesian product while preserving the keys of the outer associative array and using them in the inner ones? The result of the algorithm should be this:

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.

我看过了相当数量的笛卡尔积算法，但我被陷在如何preserve联想键的细节。目前的算法，我只用给数字索引：

I've looked up quite a number of cartesian product algorithms but I'm getting stuck on the specifics of how to preserve the associative keys. The current algorithm I am using gives numerical indices only:

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

任何帮助将是AP preciated。

Any help would be appreciated.

推荐答案

下面是一个解决方案，我不会羞于展示。

Here's a solution I wouldn't be ashamed to show.

假设我们有一个输入数组 $输入与 N 子阵列，在你的榜样。每 子阵列具有道道通项，其中 N 是它的索引中的 $输入，其关键是 Kn的。我指的是我日的 N 个子阵列 Vn的项目，我。

Assume that we have an input array $input with N sub-arrays, as in your example. Each sub-array has Cn items, where n is its index inside $input, and its key is Kn. I will refer to the ith item of the nth sub-array as Vn,i.

下面的算法可以证明通过感应工作（除非错误）：

The algorithm below can be proved to work (barring bugs) by induction:

1）对于N = 1，笛卡尔乘积简直是阵列（0 =＆GT;阵列（K1 =＆GT; v 1.1），1 =＆GT;阵列（K1 =＆GT; V1， 2），...） - 共C1项目。这可以用做一个简单的的foreach 。

1) For N = 1, the cartesian product is simply array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... ) -- C1 items in total. This can be done with a simple foreach.

2）假定 $结果已持有第N-1子阵的笛卡尔积。对 $结果与第N子阵列可以产生这样的笛卡尔乘积：

2) Assume that $result already holds the cartesian product of the first N-1 sub-arrays. The cartesian product of $result and the Nth sub-array can be produced this way:

3）在每个项目（阵列）内 $产品，添加值 KN =＆GT; VN，1 。记住所得到的产品（与添加的值）;我马上把它称作 $项目。

3) In each item (array) inside $product, add the value KN => VN,1. Remember the resulting item (with the added value); I 'll refer to it as $item.

4A）对于每个数组中 $产品：

4a) For each array inside $product:

图4b）对于组中的 VN，2每个值... VN，CN ，添加到 $产品的 $项目的副本，但改变值 KN 关键 VN，米（针对所有 2'= M＆LT; = CN ）。

4b) For each value in the set VN,2 ... VN,CN, add to $product a copy of $item, but change the value with the key KN to VN,m (for all 2 <= m <= CN).

这两个迭代4A（超过 $产品）和4b（在第N输入子阵列）结束了 $结果为 CN 的每个项目迭代收到的项目，所以最后 $结果确实包含第N次阵列的笛卡尔积。

The two iterations 4a (over $product) and 4b (over the Nth input sub-array) ends up with $result having CN items for every item it had before the iterations, so in the end $result indeed contains the cartesian product of the first N sub arrays.

因此​​，该算法将适用于任意n。

Therefore the algorithm will work for any 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));

这篇关于查找乘积PHP关联数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！