获取 PHP 数组的所有排列？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10222835/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Get all permutations of a PHP array?
提问by ohho
Given a PHP array of strings, e.g.:
给定一个 PHP 字符串数组，例如：
['peter', 'paul', 'mary']
How to generate all possible permutations of elements of this array? i.e.:
如何生成此数组元素的所有可能排列？IE：
peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter
采纳答案by Hyman
function pc_permute($items, $perms = array()) {
if (empty($items)) {
echo join(' ', $perms) . "<br />";
} else {
for ($i = count($items) - 1; $i >= 0; --$i) {
$newitems = $items;
$newperms = $perms;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
pc_permute($newitems, $newperms);
}
}
}
$arr = array('peter', 'paul', 'mary');
pc_permute($arr);
or
或者
function pc_next_permutation($p, $size) {
// slide down the array looking for where we're smaller than the next guy
for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }
// if this doesn't occur, we've finished our permutations
// the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
if ($i == -1) { return false; }
// slide down the array looking for a bigger number than what we found before
for ($j = $size; $p[$j] <= $p[$i]; --$j) { }
// swap them
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
// now reverse the elements in between by swapping the ends
for (++$i, $j = $size; $i < $j; ++$i, --$j) {
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
}
return $p;
}
$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;
do {
foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);
foreach ($perms as $p) {
print join(' ', $p) . "\n";
}
回答by MaximeW
This does what you need, in place, i.e. without allocating any additional memory. It stores the resulting permutations the $results array. I am pretty confident that this is the fasted way to solve the task.
这可以满足您的需求，即无需分配任何额外的内存。它将结果排列存储在 $results 数组中。我非常有信心这是解决任务的快速方法。
<?php
function computePermutations($array) {
$result = [];
$recurse = function($array, $start_i = 0) use (&$result, &$recurse) {
if ($start_i === count($array)-1) {
array_push($result, $array);
}
for ($i = $start_i; $i < count($array); $i++) {
//Swap array value at $i and $start_i
$t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t;
//Recurse
$recurse($array, $start_i + 1);
//Restore old order
$t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t;
}
};
$recurse($array);
return $result;
}
$results = computePermutations(array('foo', 'bar', 'baz'));
print_r($results);
This works in PHP>5.4. I used a anonymous function for recursion to keep the main function's interface clean.
这适用于 PHP>5.4。我使用匿名函数进行递归以保持主函数的界面干净。
回答by Kickstart
I needed something similar and found this post while looking. Landed up writing the following which does the job.
我需要类似的东西，并在寻找时发现了这篇文章。登陆写了下面的工作。
With 8 items it works fairly quickly (a bit quicker than the examples I found online), but go beyond that and the run time ramps up rapidly. If you only need to output the results it could be made quicker and the memory use reduced massively.
有 8 个项目，它运行得相当快（比我在网上找到的例子快一点），但除此之外，运行时间会迅速增加。如果你只需要输出结果，它可以做得更快，内存使用量会大大减少。
print_r(AllPermutations(array('peter', 'paul', 'mary')));
function AllPermutations($InArray, $InProcessedArray = array())
{
$ReturnArray = array();
foreach($InArray as $Key=>$value)
{
$CopyArray = $InProcessedArray;
$CopyArray[$Key] = $value;
$TempArray = array_diff_key($InArray, $CopyArray);
if (count($TempArray) == 0)
{
$ReturnArray[] = $CopyArray;
}
else
{
$ReturnArray = array_merge($ReturnArray, AllPermutations($TempArray, $CopyArray));
}
}
return $ReturnArray;
}
Note that the number of permutations is the factorial of the number of items in the array. For 3 items there are 6 permutations, for 4 there are 24, for 5 there are 120, for 6 there are 720, etc.
请注意，排列数是数组中项目数的阶乘。3个项目有6个排列，4个有24个，5个有120个，6个有720个等等。
EDIT
编辑
Came back to have a look at this and done some revisions.
回来看看这个并做了一些修改。
Below is an improved version of this function, which uses less storage and is quicker (quicker than other solutions I have seen).
下面是此功能的改进版本，它使用更少的存储空间并且速度更快（比我见过的其他解决方案更快）。
It takes the return array as a parameter, passing it through by reference. This reduces the amount of duplication of data as it runs through.
它将返回数组作为参数，通过引用传递它。这减少了数据运行时的重复量。
function AllPermutations($InArray, &$ReturnArray = array(), $InProcessedArray = array())
{
if (count($InArray) == 1)
{
$ReturnArray[] = array_merge($InProcessedArray, $InArray);
}
else
{
foreach($InArray as $Key=>$value)
{
$CopyArray = $InArray;
unset($CopyArray[$Key]);
AllPermutations2($CopyArray, $ReturnArray, array_merge($InProcessedArray, array($Key=>$value)));
}
}
}
回答by Tschallacka
I expanded a bit on the answer of Hyman
我对Hyman的回答进行了扩展
function pc_permute($items, $perms = [],&$ret = []) {
if (empty($items)) {
$ret[] = $perms;
} else {
for ($i = count($items) - 1; $i >= 0; --$i) {
$newitems = $items;
$newperms = $perms;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
$this->pc_permute($newitems, $newperms,$ret);
}
}
return $ret;
}
This will actually return an array with all possible permutations.
这实际上将返回一个包含所有可能排列的数组。
$options = ['startx','starty','startz','endx','endy','endz'];
$x = $this->pc_permute($options);
var_dump($x);
[0]=>
array(6) {
[0]=>
string(6) "startx"
[1]=>
string(6) "starty"
[2]=>
string(6) "startz"
[3]=>
string(4) "endx"
[4]=>
string(4) "endy"
[5]=>
string(4) "endz"
}
[1]=>
array(6) {
[0]=>
string(6) "starty"
[1]=>
string(6) "startx"
[2]=>
string(6) "startz"
[3]=>
string(4) "endx"
[4]=>
string(4) "endy"
[5]=>
string(4) "endz"
}
[2]=>
array(6) {
[0]=>
string(6) "startx"
[1]=>
string(6) "startz"
[2]=>
string(6) "starty"
[3]=>
string(4) "endx"
[4]=>
string(4) "endy"
[5]=>
string(4) "endz"
}
[3]=>
array(6) {
[0]=>
string(6) "startz"
[1]=>
string(6) "startx"
[2]=>
string(6) "starty"
[3]=>
string(4) "endx"
[4]=>
string(4) "endy"
[5]=>
string(4) "endz"
}
[4]=>
array(6) {
[0]=>
string(6) "starty"
[1]=>
string(6) "startz"
[2]=>
string(6) "startx"
[3]=>
string(4) "endx"
[4]=>
string(4) "endy"
[5]=>
string(4) "endz"
}
[5]=>
array(6) {
[0]=>
string(6) "startz"
[1]=>
string(6) "starty"
[2]=>
string(6) "startx"
[3]=>
string(4) "endx"
[4]=>
string(4) "endy"
[5]=>
string(4) "endz"
}
[6]=> ................ a lot more
I found it a bit more usefull to get an array back instead of a string. Then it's up to the using application how to handle the resutls(to join them, or something else)
我发现获取数组而不是字符串更有用。然后取决于使用应用程序如何处理结果（加入它们或其他东西）
回答by baa2w
Simple version with recursion and no artificial extra arguments:
带有递归的简单版本，没有人为的额外参数：
function permuteArray(array $input) {
$input = array_values($input);
// permutation of 1 value is the same value
if (count($input) === 1) {
return array($input);
}
// to permute multiple values, pick a value to put in the front and
// permute the rest; repeat this with all values of the original array
$result = [];
for ($i = 0; $i < count($input); $i++) {
$copy = $input;
$value = array_splice($copy, $i, 1);
foreach (permuteArray($copy) as $permutation) {
array_unshift($permutation, $value[0]);
$result[] = $permutation;
}
}
return $result;
}
This algorithm is nice and instructive how you would do it on paper, but otherwise very inefficient as it calculates same permutations multiple times. Not to say that it is very impractical for calculating permutations of larger arrays as the space and number of calculations grow exponentially.
这个算法很好，很有指导意义，你将如何在纸上完成它，但否则效率很低，因为它多次计算相同的排列。并不是说随着计算的空间和数量呈指数增长，计算更大数组的排列是非常不切实际的。
