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

php permutaciones

Question

Necesito un algoritmo que devuelva todas las combinaciones posibles de todos los caracteres en 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 solo devuelve la misma combinación de cantidad que la longitud de la cadena.

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

Answer 1

Colocaría todos los caracteres en una matriz y escribiría una función recursiva que ''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 = orden no importa. permutaciones = el orden sí importa.

Así que, oye, todos son la misma combinación, pero 3 permutaciones separadas como se mencionó. 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 2

Mi enfoque utiliza la recursividad y no hay bucles, por favor revise y dé su opinió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");

Answer 3

Mi variante (funciona también con la 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;
}

PD: Downvoter, explique su posición. Este código usa funciones estándar str_split y array_diff_key adicionales, pero este fragmento de código es el más pequeño , implementa la recursividad de cola pura con solo un parámetro de entrada y es isomorfo al tipo de datos de entrada.

Tal vez pierda 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 una de las diferentes alternativas que tiene su propias ventajas?

Answer 4

Puede utilizar un enfoque basado en el seguimiento posterior para 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