获取一个PHP数组的所有排列？
给定一个string的PHP数组，例如：
['peter', 'paul', 'mary'] 如何生成这个数组元素的所有可能的排列？ 即：
peter-paul-mary peter-mary-paul paul-peter-mary paul-mary-peter mary-peter-paul mary-paul-peter
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);
要么
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"; }
我需要类似的东西，find这个职位，而期待。 写下以下这个工作。
有8个项目，它的工作速度相当快（比我在网上find的例子快一点），但超越这个，运行时间迅速增加。 如果你只需要输出结果就可以更快，而且内存使用量大大减less。
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; }
请注意，排列的数量是数组中项目数的阶乘。 3个项目有6个排列，4个有24个，5个有120个，有6个有720个，等等。
这就是你需要的地方，即不分配任何额外的内存。 它存储结果排列$ 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);
这在PHP> 5.4中工作。 我使用匿名函数recursion来保持主函数的接口清洁。
我扩大了一点杰克的答案
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; }
这将实际上返回一个数组与所有可能的排列。
$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
我发现它更有用，而不是一个string返回一个数组。 然后，这是由使用应用程序如何处理resutls（join他们，或其他）
简单的版本与recursion和没有人为的额外的参数：
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; }
这个algorithm是很好的和有启发性的，你将如何在纸上做，但是否则效率很低，因为它会多次计算相同的排列。 并不是说计算更大arrays的排列是非常不切实际的，因为空间和计算的数量呈指数增长。
