¿Cómo generar todas las permutaciones de una cadena en PHP?

Question

Necesito un algoritmo que devuelve toda combinación posible de todos los caracteres de una cadena.

He intentado:

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

Pero eso sólo devuelve la misma cantidad de combinación como la longitud de la cadena.

Diga el $input = "hey", el resultado sería: hey, hye, eyh, ehy, yhe, yeh.

Answer 1

Se puede utilizar una vuelta enfoque basado en el seguimiento de generar sistemáticamente todas las permutaciones:

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

Salida:

#php a.php 
hey 
hye 
ehy 
eyh 
yeh 
yhe 

Answer 2

me gustaría poner todos los caracteres en una matriz, y escribir una función recursiva eso 'raya' a todos los personajes restantes. Si la matriz está vacía, a una matriz de referencia pasada.

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

Imprime:

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

Ah sí, combinaciones = fin doens't materia. permutations = el orden sí importa.

Así que bueno, hye Yeh son todos la misma combinación, pero 3 permutaciones separados como se ha mencionado. Tenga en cuenta que la escala de elementos sube muy rápido. Se llama factorial, ¡y está escrito como 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720 elementos (para una cadena de 6 caracteres). Una cadena de 10 caracteres será 10! = 3628800 permutaciones ya, que es una matriz muy grande. ¡En este ejemplo es 3! = 3 * 2 * 1 = 6.

Answer 3

Mi variante (funciona tan bien con matriz o entrada de cadena)

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, explique su posición. Este código utiliza str_split y array_diff_key funciones estándar adicionales, pero este fragmento de código es el más pequeño , implementa pura recursividad cola con un solo parámetro de entrada y es isomorfo al tipo de datos de entrada.

Tal vez perderá puntos de referencia un poco cuando se compara con otras implementaciones (pero el rendimiento es casi el mismo que en la respuesta de @ codaddict para varias cadenas de caracteres), pero ¿por qué no podemos simplemente considerarlo como uno de los diferentes alternativas que tiene sus propias ventajas?

Answer 4

Mi enfoque utiliza la recursividad y no hay bucles, por favor, comprobar y dar retroalimentación:

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