Come generare tutte le permutazioni di una stringa in PHP?

Question

Ho bisogno di un algoritmo che restituisca tutte le combinazioni possibili di tutti i caratteri in una stringa.

ho provato:

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

Ma che restituisce solo la stessa combinazione quantità come la lunghezza della stringa.

Dire il $input = "hey", il risultato sarebbe: hey, hye, eyh, ehy, yhe, yeh.

Answer 1

È possibile utilizzare un back di monitoraggio approccio basato per generare sistematicamente tutte le permutazioni:

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

uscita:

#php a.php 
hey 
hye 
ehy 
eyh 
yeh 
yhe 

Answer 2

vorrei mettere tutti i personaggi in un array, e scrivere una funzione ricorsiva che "spoglierà" tutti i restanti personaggi. Se la matrice è vuota, su una matrice di riferimento passata.

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

Stampe fuori:

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

Ah, sì, combinazioni = ordine materia doens't. permutazioni = l'ordine conta.

Così hey, yeh hye sono tutti la stessa combinazione, ma 3 permutazioni particolare di cui. Fai attenzione che la scala degli oggetti sale molto velocemente. Si chiama fattoriale, ed è scritto come 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720 elementi (per una stringa di 6 caratteri). Una stringa di 10 caratteri sarà 10! = 3628800 permutazioni già, che è un array molto grande. In questo esempio è 3! = 3 * 2 * 1 = 6.

Answer 3

mio variante (funziona anche con array o stringhe di 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, si prega di spiegare la vostra posizione. Questo codice utilizza ulteriori str_split e array_diff_key funzioni standard, ma questo frammento di codice è il più piccolo , implementa puro coda ricorsione con un solo parametro di input ed è isomorfo al tipo di dati in ingresso.

Forse perderà un po 'i benchmark quando si confrontano con altre implementazioni (ma le prestazioni sono praticamente le stesse della risposta di @ codaddict per diverse stringhe di caratteri), ma perché non possiamo semplicemente considerarlo come uno dei diversi alternative che ha i suoi vantaggi?

Answer 4

Il mio approccio utilizza la ricorsione e nessun cicli, si prega di controllare e dare un 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");