如何在PHP中生成一个string的所有排列?

我需要一个algorithm返回一个string中所有字符的所有可能的组合。

我试过了:

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

但是,只返回与string长度相同的数量组合。

说出$input = "hey" ,结果是: hey, hye, eyh, ehy, yhe, yeh

您可以使用基于回溯的方法来系统地生成所有排列:

 // 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. 

输出:

 #php a.php hey hye ehy eyh yeh yhe 

我的变体(与数组或stringinput一起工作)

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

PS: Downvoter,请解释你的立场。 这段代码使用了额外的str_splitarray_diff_key标准函数,但是这个代码片段是最小的 ,它只用一个input参数实现了纯粹的尾recursion ,并且和input数据types是同构的。

当与其他实现进行比较时,它可能会失去一些基准(但性能实际上与@ codaddict对几个string的答案几乎相同),但是为什么我们不能把它看作是其中一种不同的方法自己的优势?

我会把所有的字符放在一个数组中,然后写一个recursion函数,将所有剩下的字符“去掉”。 如果数组是空的,则返回一个引用传递的数组。

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

打印出来:

 Array ( [0] => h [1] => e [2] => y ) Array ( [0] => hey [1] => hye [2] => ehy [3] => eyh [4] => yhe [5] => yeh ) 

啊,是的,组合=顺序doens't重要。 排列顺序很重要。

所以,嘿嘿,你们都是一样的组合,但是提到了3个不同的排列组合。 注意项目的规模增长非常快。 这就是所谓的阶乘,写成6! = 6 * 5 * 4 * 3 * 2 * 1 = 720个项目(对于6个字符的string)。 一个10个字符的string将是10! = 3628800已经排列,这是一个非常大的数组。 在这个例子中是3! = 3 * 2 * 1 = 6。

我的方法使用recursion和无循环,请检查并提供反馈:

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