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

非常感谢帮助。

- Lotus Notes

---

相关文章：在PHP中连接n个数组的值（2010年2月） - hakre

这似乎是一个转置操作，而不是笛卡尔积。 - XuDing

看看nSPL中的cartesianProduct。 - Ihor Burlachenko

Answer 1

原理

假设我们有一个输入数组$input，其中包含N个子数组，就像你的例子一样。每个子数组都有Cn个项目，其中n是它在$input中的索引，其键为Kn。我将把第n个子数组的第i个项目称为Vn,i。

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

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

假设$result已经保存了前N-1个子数组的笛卡尔积。可以通过以下方式生成$result和第N个子数组的笛卡尔积：

在$product中的每个项目（数组）中，添加值KN => VN,1。记住结果项目（添加了值的项目）；我将称之为$item。

4a) 对于$product中的每个数组：

4b) 对于集合中的每个值VN,2 ... VN,CN，将$item的副本添加到$product中，但将键为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));

- Jon

---

你这样写 while (list($key, $values) = each($input)) { 有什么原因吗？为什么不用 foreach ($input as $key => $values) { 呢？ - Dave2081

@FunBeans：没有什么原因。其实我自己也很惊讶我选择那样写，尽管那是几年前的事了。 - Jon

Answer 2

这是@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

- Sergiy Sokolenko

---

这项技术返回的产品顺序符合我的期望，而被接受的答案却不是。 - Matthew

@Matthew，感谢您注意到这一点，我想这是因为“array_merge”在被接受的解决方案中使用了。 - Sergiy Sokolenko

运行正常！谢谢！ - Shankar Thiyagaraajan

它运行得很好，我觉得它比被接受的答案更优雅。 - Vincent

恭喜您，您的实现现在已经被用于 Laravel 中。 :) - Gras Double

Answer 3

为什么不使用递归生成器...内存问题几乎没有（而且它很美）

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(array $a)
{
    if ($a) {
        $k = array_key_last($a);
        if ($u = array_pop($a)) {
            foreach (acartesian($a) as $p) {
                foreach ($u as $v) {
                    yield $p + [$k => $v];
                }
            }
        }
    } else {
        yield[];
    }
}

- Titus

---

调用栈怎么样？嵌套调用的最大深度是多少？ - Constantin Galbenu

@ConstantinGALBENU PHP的默认设置没有限制，但这是一个好的观点。也许有一天我会测试内存消耗。 - Titus

我问这个问题是因为在您的情况下，调用堆栈与输入数组中level0项的数量相等，这可能会在长数组中成为一个问题。 - Constantin Galbenu

优美高效的解决方案！+12345 - mpyw

嗨，Titus，你的解决方案已经被移植并增强到一个专用库中：https://github.com/bpolaszek/cartesian-product（添加了一个count()方法来计算组合数而不必迭代）。非常感谢你！ - Ben

Answer 4

在 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;
}

- freytag

Answer 5

以下是我的翻译：

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')]

< p > 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;
}

- deceze

Answer 6

如果内存消耗很重要或者你最终不需要所有的组合，可以使用迭代器逐个生成一个组合。如果需要所有的组合，可以使用 iterator_to_array。

function cartezianIterator($inputArray)
{
    $maximumPosition = array_map('count', $inputArray);
    $position = array_pad([], count($inputArray), 0);

    while (false !== ($item = buildItemAtPosition($inputArray, $position))) {

        yield $item;

        $position = incrementPosition($position, $maximumPosition);
    }
}

function buildItemAtPosition($inputArray, $positions)
{
    if ($positions[0] >= count($inputArray[0])) {
        return false;
    }

    $item = [];
    foreach ($inputArray as $rowIndex => $row) {
        $position = $positions[$rowIndex];

        $item[] = $row[$position];
    }

    return $item;
}

function incrementPosition($position, $maximumPosition)
{
    $digitToIncrement = count($position) - 1;

    do {
        $position[$digitToIncrement]++;

        if ($position[$digitToIncrement] < $maximumPosition[$digitToIncrement] || 0 === $digitToIncrement) {
            //no overflow
            break;
        }

        //overflow, reset to zero and increment parent digit
        $position[$digitToIncrement] = 0;

        $digitToIncrement--;
    } while ($digitToIncrement >= 0);

    return $position;
}

然后，要一次获取一个解决方案，您可以使用 foreach 或 next，像这样：

$iterator = cartezianIterator($inputArray);

//of course, you need to do something with the result...
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);

如果你只需要几个组合，那么这个解决方案非常快速。此外，内存消耗非常低（它使用一个平坦的数组来存储一些整数）。

注意：不使用递归函数。

- Constantin Galbenu

Answer 7

另一个解决方案：

function getAllVariations($input) {
    $result = array();
    $cnt = array_product(array_map('count', $input));
    $step = 1;
    foreach ($input as $key=>$array) {
        for ($i=0; $i<$cnt; $i++) {
            foreach ($array as $value) {
                for ($k=0; $k<$step; $k++) {
                    $result[$i+$k][$key] = $value;
                }
                $i += $step;
            }
            $i--;
        }
        $step = $step * count($array);
    }
    return $result;
}

使用方法：

$input = array(
    'arm' => array('A', 'B', 'C'),
    'gender' => array('Female', 'Male'),
    'location' => array('Vancouver', 'Calgary'),
    'name' => array('Rio', 'Mark')
);

echo "<pre>";
var_dump(getAllVariations($input));

- Respant

Answer 8

我快速调整了您的代码，我的尝试可能有些粗糙，但请看看这是否符合您的要求：

$result = array();
$nm = '';
foreach ($map as $name => $a) {
    if (empty($result)) {
        $result = $a;
        $nm = $name;
        continue;
    }

    $res = array();
    foreach ($result as $r) {
        foreach ($a as $v) {
            $myr = $r;
            $myv = $v;
            if(!is_array($r)) $myr = array($nm => $r);
            if(!is_array($v)) $myv = array($name => $v);

            $res[] = array_merge($myr, $myv);
        }
    }
    $result = $res;
}
echo "<pre>";
print_r($result);

- Sabeen Malik

Answer 9

为什么不使用数据库来完成这个任务呢？

在MySQL中很容易实现。

table arm
   id integer primary key
   label char

table gender
   id integer primary key
   gender enum('male','female')

table location
   id integer primary key
   city varchar(255)

然后执行一个查询

$query = mysql_query(" 
  SELECT a.label, g.gender, l.city
  FROM arm a
  CROSS JOIN gender g
  CROSS JOIN location l
  ORDER BY a.id
") or die("Could not execute query");

while($row = mysql_fetch_array($query) )
{
   ....
}

并将其读出：

- Johan

---

感谢您的解决方案，但我无法在数据库中解决这个特定的问题。如果以后有需要，我一定会参考您的查询。 - Lotus Notes

Answer 10

一个算法是在每一步中使用当前步骤的项目来扩展先前结果：

function cartezian1($inputArray)
{
    $results = [];

    foreach ($inputArray as $group) {
        $results = expandItems($results, $group);
    }

    return $results;
}

function expandItems($sourceItems, $tails)
{
    $result = [];

    if (empty($sourceItems)) {
        foreach ($tails as $tail) {
            $result[] = [$tail];
        }
        return $result;
    }

    foreach ($sourceItems as $sourceItem) {
        foreach ($tails as $tail) {
            $result[] = array_merge($sourceItem, [$tail]);
        }
    }

    return $result;
}

这个解决方案使用内存来存储所有的组合，然后一次性返回它们。因此，它很快，但需要大量的内存。此外，没有使用递归函数。

- Constantin Galbenu