如何在 PHP 中生成一个字符串的所有排列？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2617055/
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
How to generate all permutations of a string in PHP?
提问by Johan
I need an algorithm that return all possible combination of all characters in one string.
我需要一种算法来返回一个字符串中所有字符的所有可能组合。
I've tried:
我试过了：
$langd = strlen($input);
for($i = 0;$i < $langd; $i++){
$tempStrang = NULL;
$tempStrang .= substr($input, $i, 1);
for($j = $i+1, $k=0; $k < $langd; $k++, $j++){
if($j > $langd) $j = 0;
$tempStrang .= substr($input, $j, 1);
}
$myarray[] = $tempStrang;
}
But that only returns the same amount combination as the length of the string.
但这仅返回与字符串长度相同的数量组合。
Say the $input = "hey", the result would be: hey, hye, eyh, ehy, yhe, yeh.
说$input = "hey"，结果将是：hey, hye, eyh, ehy, yhe, yeh。
回答by codaddict
You can use a back tracking based approach to systematically generate all the permutations:
您可以使用基于回溯的方法来系统地生成所有排列：
// function to generate and print all N! permutations of $str. (N = strlen($str)).
function permute($str,$i,$n) {
if ($i == $n)
print "$str\n";
else {
for ($j = $i; $j < $n; $j++) {
swap($str,$i,$j);
permute($str, $i+1, $n);
swap($str,$i,$j); // backtrack.
}
}
}
// function to swap the char at pos $i and $j of $str.
function swap(&$str,$i,$j) {
$temp = $str[$i];
$str[$i] = $str[$j];
$str[$j] = $temp;
}
$str = "hey";
permute($str,0,strlen($str)); // call the function.
Output:
输出：
#php a.php
hey
hye
ehy
eyh
yeh
yhe
回答by zavg
My variant (works as well with array or string input)
我的变体（也适用于数组或字符串输入）
function permute($arg) {
$array = is_string($arg) ? str_split($arg) : $arg;
if(1 === count($array))
return $array;
$result = array();
foreach($array as $key => $item)
foreach(permute(array_diff_key($array, array($key => $item))) as $p)
$result[] = $item . $p;
return $result;
}
P.S.:Downvoter, please explain your position. This code uses additional str_splitand array_diff_keystandard functions, but this code snippet is the smallest, it implements pure tail recursionwith just one input parameter and it is isomorphicto the input data type.
PS：Downvoter，请说明你的立场。这段代码使用了额外的str_split和array_diff_key标准的函数，但是这个代码片段是最小的，它只用一个输入参数实现了纯尾递归，并且与输入数据类型同构。
Maybe it will lose benchmarks a little when comparing with other implementations (but performance is actually almost the same as in @codaddict's answer for several character strings), but why we can't we just consider it as one of the different alternatives which has its own advantages?
与其他实现相比，它可能会失去一些基准（但性能实际上与@codacci 对几个字符串的回答几乎相同），但是为什么我们不能将其视为具有其特性的不同替代方案之一自身优势？
回答by Hans
I would put all the characters in an array, and write a recursive function that will 'stripe out' all the remaining characters. If the array is empty, to a reference passed array.
我会将所有字符放在一个数组中，并编写一个递归函数，该函数将“删除”所有剩余字符。如果数组为空，则以引用传递数组。
<?php
$input = "hey";
function string_getpermutations($prefix, $characters, &$permutations)
{
if (count($characters) == 1)
$permutations[] = $prefix . array_pop($characters);
else
{
for ($i = 0; $i < count($characters); $i++)
{
$tmp = $characters;
unset($tmp[$i]);
string_getpermutations($prefix . $characters[$i], array_values($tmp), $permutations);
}
}
}
$characters = array();
for ($i = 0; $i < strlen($input); $i++)
$characters[] = $input[$i];
$permutations = array();
print_r($characters);
string_getpermutations("", $characters, $permutations);
print_r($permutations);
Prints out:
打印出来：
Array
(
[0] => h
[1] => e
[2] => y
)
Array
(
[0] => hey
[1] => hye
[2] => ehy
[3] => eyh
[4] => yhe
[5] => yeh
)
Ah yes, combinations = order doens't matter. permutations = order does matter.
啊，是的，组合 = 顺序无关紧要。排列 = 顺序很重要。
So hey, hye yeh are all the same combination, but 3 separate permutations as mentioned. Watch out that the scale of items goes up very fast. It's called factorial, and is written like 6! = 6*5*4*3*2*1 = 720 items (for a 6 character string). A 10 character string will be 10! = 3628800 permutations already, which is a very big array. In this example it's 3! = 3*2*1 = 6.
所以嘿，hye yeh 都是相同的组合，但如上所述有 3 个单独的排列。注意项目的规模增长得非常快。它被称为阶乘，写成 6！= 6*5*4*3*2*1 = 720 项（对于 6 个字符的字符串）。一个 10 个字符的字符串将是 10！= 3628800 个排列，这是一个非常大的数组。在这个例子中是 3！= 3*2*1 = 6。
回答by Gaurav Pandey
My approach uses recursion and no loops, please check and give feedback:
我的方法使用递归并且没有循环，请检查并提供反馈：
function permute($str,$index=0,$count=0)
{
if($count == strlen($str)-$index)
return;
$str = rotate($str,$index);
if($index==strlen($str)-2)//reached to the end, print it
{
echo $str."<br> ";//or keep it in an array
}
permute($str,$index+1);//rotate its children
permute($str,$index,$count+1);//rotate itself
}
function rotate($str,$index)
{
$tmp = $str[$index];
$i=$index;
for($i=$index+1;$i<strlen($str);$i++)
{
$str[$i-1] = $str[$i];
}
$str[$i-1] = $tmp;
return $str;
}
permute("hey");
