Как сгенерировать все перестановки строки в PHP?

Вы можете использовать подход, основанный на обратном отслеживании, для систематического создания всех перестановок:

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

Мой вариант (работает также с массивом или строковым вводом)

 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_split и array_diff_key , но этот фрагмент кода является наименьшим , он реализует чистую хвостовую рекурсию только с одним входным параметром и изоморфен типу входных данных.

Может быть, он немного потеряет тесты при сравнении с другими реализациями (но производительность на самом деле почти такая же, как в ответе @ codaddict для нескольких строк символов), но почему мы не можем просто рассматривать ее как одну из альтернатив, которая имеет собственные преимущества?

Я бы поместил все символы в массив и написал рекурсивную функцию, которая «вычеркнет» все остальные символы. Если массив пуст, в массив, переданный по ссылке.

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

Ах да, комбинации = порядок не имеет значения. перестановки = порядок имеет значение.

Итак, эй, hye yeh – все те же комбинации, но три отдельные перестановки, как упоминалось. Остерегайтесь того, что масштаб предметов растет очень быстро. Он называется факториалом и написан как 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720 элементов (для 6-символьной строки). Строка из 10 символов будет равна 10! = 3628800 перестановок уже, что очень большой массив. В этом примере это 3! = 3 * 2 * 1 = 6.

Мой подход использует рекурсию и отсутствие циклов, пожалуйста, проверьте и дайте отзыв:

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