Generar todas las combinaciones posibles

[jordifreek]

Cordiales saludos.

Me han solicitado, un poco en plan reto, que genere todas las combinaciones posibles de letras en una cadena de 5 caracteres, es decir, teniendo el abecedario, de la 'a' a la 'z', generar todas las palabras posibles:

aaaaa
aaaab
aaaac
aaaad
[...]
avion
[...]
coche
[...]
zzzzz

Ando buscando algun procedimiento, sugerencia y a poder ser algun codigo o algoritmo que lo resuelva. Yo he probado de diferentes formas, creando arrays y pasandolos por bucles, pero no lo consigo.

Me supone todo un reto y no consigo dar con la solucion.

De ante mano muchas gracias!

[vevni]

eso es reto de algoritmos, en matematicas hay funciones establecidad osea a detalladas para hacer combinaciones seria bueno que hecharas una leida y de ahi lo aplikes a la programacion, recuerdo por ejemplo que hay una formula para sacar la raiz cuadrada y si es exacta bueno por algunos digitos, tambien para sacar la sumatoria de numeros seguids por ejemplo del 1 al 100, hay un metodo que desarrollo gaus desde niño y es esa, jejeje pero no recuerdo la formula, a klo que voy es que para combinaciones ya hay uno de finidido matematicamente solo es cuestion de adaptarlo, osea cosa de nada...... jejeje!

[Carlojas]

Para hacer lo que deseas puedes utilizar formulas estadisticas como la permutacion y la combinacion solo basta que analizes las formulas y plantees el algoritmo aqui te dejo en link para que comiences con tu trabajo

http://www.itch.edu.mx/academic/indu...mutaciones.htm

Saludos y espero que te sirva.

[_ssx]

tomando como base la combinatoria.. tendrias esto.. ya que tu planteamiento no se basa en palabras Gramaticamente correctas si no simples combinaciones de las letras y con repetición tendrias esto..

1.- la primera letra puede tomar 27 valores de la A a la Z
2.- la segunda igual
3.- la tercera igual
4.- la cuarta igual
5.- la quinta igual..

Si te das cuenta el numero total de combinaciones seria..

27 x 27 x 27 x 27 x 27 = 387420489

seria hacer un for anidado..

[vevni]

HICISTE RECORDAR MIS VIEJOS TIEMPOS DE LA UNIVERSIDAD, JAJAJAA CUALES VIEJOS TIEMPOS ACABO DE SALIR, JAJAAJ, ESE TIPO DE ALGORITOS LOS HACIAMOS CON C.
CLARO UN POCO MAS TEDIOSITO...
SOLO UN POCO YA QYE LAS CADENAS SON TRATADAS COMO UNA SECUENCIA DE CARACTERES, JEJEJEE.
ESPERO SEA LA SOLUCION A TU PROBLEMA....

Código PHP:

  $cad_p="avion";
       $cad_temp;


       $tam_cad=strlen($cad_p);

        echo"<H1>Palabra: $cad_p</H1>";
       for($cont=0; $cont<$tam_cad; $cont++)
       {
               $cad_tmp=$cad_p;
               $letra='A';
               for($cont2=0; $cont2<26; $cont2++) /*for($cont2='a'; $cont2<='z'; $cont2++)*/
               {
                   
                   $cad_tmp[$cont]=$letra;
                   $cad_temp2=$cad_tmp;
                   echo "$cad_temp2 - $cont - $cont2";
                   echo"<br>";
                   $letra++;
                   
               }
               echo"<hr>";
       }
?> 
  

[vevni]

Es Totalmente Funcional, Lo Acabo De Hacer Ahorita,
Al Principio Defino La Cadena, Y Defino Una Variable Temporal..

Despues Obtengo La Long De Esa Cadena, Pues Me Servira Para Hacer La Iteracion...

Por Ende Se Nos Ocurre Que Deben Ser 2 Iteraciones Una Que Haga Que Cambie La Letra Del Alfabeto Y Otra Que Haga Que Cambie La Posicion..

El Primero While Es Para Cambiar De Posicion Y El While Mas Interno Es Para La Letra Del Alfabeto..

Lo Que Hago Antes De Entrar Al 2do While Es Tomo La Cadena Original Y Hago Una Copia, Despues A La Variable Letra La Defino Como A...

Despues Cuando Entro Al Bucle Accedo Ala Copia De La Cadena En Forma De Array
Entonces Como El 1er While Lleva El Contador De Posiciones El Me Da La Pauta Para Ir Cambiando La Posicion, Y Pues Simplemente Digo Ala Cadena Tal, En La Posicion Tal Asignale La Letra Tal...

Despues Ala Varianle Temp2 Le Asigno La Cadnea Ya Con La Letra Cambiada Y La Imprimo....
Hago Un Salto
Y Actualizo La Letra, Esto Se Debe A Que Las Letras Son Tomadas Como Valores Enteros Deacuerdo A Su Correspondiente Valor Ascii, Es Por Eso Que Le Puedo Sumar Y Decrementar, Y Asi Se La Lleva Con Cada Letra..

Espero Sea Comprensible, Claro Cada Quien Lo Hace Como Le Gusta Y Como Se Le Ocurra , Eso Es Lo Bonito De Los Algoritmos Mil Y Una Forma De Hacerlo Pero Al Final De Todo Se Llega Con El Resultado...

Ejjeje Saludos, Y Dime Si Te Fue Util Y Si Eso Es Lo Que Bbuscabas...!!!!

[vevni]

LAS OTRAS VARIABLES QUE PUSE EN EL echo, eran nadamas para ver que onda, jejeje quitalas, esk me paso algo, hice una primera vercion, es funcional, pero, me hacia dos veces el ciclo, ahora pongo el codigo...

Código PHP:

  $cad_p="avion";
       $cad_temp;


       $tam_cad=strlen($cad_p);

        echo"<H1>Palabra: $cad_p</H1>";
       for($cont=0; $cont<$tam_cad; $cont++)
       {
               $cad_tmp=$cad_p;
               
               for($cont2='a'; $cont2<='z'; $cont2++)
               {
                   
                   $cad_tmp[$cont]=$cont2;
                   $cad_temp2=$cad_tmp;
                   echo "$cad_temp2 - $cont - $cont2";
                   echo"<br>";
               
               }
               echo"<hr>";
       }
?> 
  

no se pork hace todo doble, le puse esas dos variables para ver que valores tomaban y me di cuenta que la variable del caracter hacia doble ciclo, se supone que al llegar ala z, deberia salir e incrementar el valor del bucle anterior, pero no lo hace, bueno si, pero antes lo hace 2 veces, verifikenlo, kisas pork me duele la cabeza y no eh comido por eso ya me blokee, mirenlo y diganme en k me ekivoke segun yo asi nadamas funciona, ejecutenlo para que vean lo que hace, jeejeje saludos!!!

[jordifreek]

Esto se me esta convirtiendo en un problema "auto-personal", es mas complejo de lo que yo pensaba y veo que voy a tener que retomar algunos estudios de combinatorias.

_ssx, no estoy seguro pero me parece que tu planteamineto, por lo que estoy viendo, no es correcto.

carlojas, gracias por ese link, lo estudiaré a fondo.

vevni, tu segundo codigo tiene buena pinta, pero falla en algo. Parece que con los dos caracteres si que genere todas las posibildiades, pero con 5 caracteres no lo hace y creo que es debido a que solo tienes en cuenta el cambio cada vez en una posicion diferente y en ocasiones hace falta tener en cuenta varias posiciones (hasta 5).

Mi cabeza ya esta tirando humo... como digo, voy a mirar algo de combinatorias, y a ver si hay suerte.

Muchisimas gracias por vuestras respuestas y cualquier otra idea que podais tener será bienvenida.

[cybersersupremo]

usando un poco la logica esto es sencillisimo, solo tienes k hacer 5 fors uno dentro de otro
for($a='a'; $a<='z'; $a++)
for($e='a'; $e<='z'; $e++)
for($i='a'; $i<='z'; $i++)
for($o='a'; $o<='z'; $o++)
for($u='a'; $u<='z'; $u++)
y ahi la cadena resltando es $a$e$i$o$u

[vevni]

pero el primer codigo que puse si es funcional.......
no lo has probado?.........
jajajaaja lo puse estatico, osea la palabra avion, conviertelo a funcion y ya y recibes el parametro, para eso sirve la funcion strlen para que funcione sobre cualquier cadena.!!

[vevni]

5 fors? y que pasa si son diferentes palabras????????????????????
diferentes tamaños?

[vevni]

Código PHP:

  $cad_p="avion";
       $cad_temp;


       $tam_cad=strlen($cad_p);

        echo"<H1>Palabra: $cad_p</H1>";
       for($cont=0; $cont<$tam_cad; $cont++)
       {
               $cad_tmp=$cad_p;
               $letra='A';
               for($cont2=0; $cont2<26; $cont2++) /*for($cont2='a'; $cont2<='z'; $cont2++)*/
               {
                   
                   $cad_tmp[$cont]=$letra;
                   $cad_temp2=$cad_tmp;
                   echo "$cad_temp2 - $cont - $cont2";
                   echo"<br>";
                   $letra++;
                   
               }
               echo"<hr>";
       }
?> 
  

como te digo este es totalmente funcional es mi 2da version, la primera version es la que me fallaba...... ya probaste este codigo????????????

quieres que sea para mas cadenas??? ponlo en una funcion y tomas como parametro la cadena y listo.... o cambia la palabra avion y has pruebas con las demas..!! saludos!!

[_ssx]

Iniciado por cybersersupremo

usando un poco la logica esto es sencillisimo, solo tienes k hacer 5 fors uno dentro de otro
for($a='a'; $a<='z'; $a++)
for($e='a'; $e<='z'; $e++)
for($i='a'; $i<='z'; $i++)
for($o='a'; $o<='z'; $o++)
for($u='a'; $u<='z'; $u++)
y ahi la cadena resltando es $a$e$i$o$u

si, esto es lo mas cercano a lo que pidio.. vientos aunque no se cuanto tarde en procesar, tantas combinaciones

Código PHP:

  <?php
for($a='a'; $a<='z'; $a++)
for($e='a'; $e<='z'; $e++)
for($i='a'; $i<='z'; $i++)
for($o='a'; $o<='z'; $o++)
for($u='a'; $u<='z'; $u++)
echo $a.$e.$i.$o.$u."<br>";
       ?>   

[jordifreek]

cybersersupremo, jejeje, hay que ver que lógica!! parece que si va (aunque llega un momento en que empieza a generar mas de 5 caracteres, no por ello representa un problema), no lo he podido probar correctamente, mi portatil intel celeron a 1.7 con 1 giga de ram se queda colgao al procesar tanto bucle aun siendo que le aumente el tiempo maximo de ejecución de script a 3000 segundos (en php.ini), cuando este en casa lo probaré con el PC.

Vevni, no hace correctamente lo que propuse... creo que el primer error que cometes es tomar como referencia la palabra avion, no obstante agradezco muchisimo tu interes!!!

[cybersersupremo]

vevni el no ha pedido ni diferentes palabras ni diferentes tamaños, de todas formas es la fomra mas fácil, y e simposible que genere mas de 5 caracteres, eso generará todas las combinacione sposibles, pero posiblemente te pete algun que otro pc, prueba a meterle algun sleep, en algun for de los ultimos

Código PHP:

  <?php
for($a='a'; $a<='z'; $a++){
  for($e='a'; $e<='z'; $e++){
    for($i='a'; $i<='z'; $i++){
      for($o='a'; $o<='z'; $o++){
         for($u='a'; $u<='z'; $u++){
                  echo $a.$e.$i.$o.$u."<br>";
         }
       }
     }
   }
}
 
 
       ?>   

[vevni]

-.-
y no eres capaz de cambiarle la palabra base avion a otra????
segun entendo era

aaaaa
aaaab
aaaac
aaaad
aaaaz

aaaaa
baaaa
caaaa
daaaa

digo cosas como esa, en serio, alo mejor o soy tonto o que sop,
en ves de avion pon la frase que tu quieras, no solo sirve para 5 caracteres si no par N.

claro por eso te digo si tu planteamiento inicial fue ese, porque dices que no funciona bien,
o dime que es lo que genera mal??? o porque esta mal mi planteamiento.....
sus fors anidados del codigo anterior.........
hace lo mismo que el mio solo que el mio se basa en la long de la cadena como base,

-.- cambia dentro del for y pon contador=0 y contador<5; es todoooo,

[vevni]

jajaaja corriendo el script del los 5 fors comprendi que deseaba, sorry es que me fie de tu ejemplo y no comprendi, jejeejej se tardo como 60 segundos y se murio el script, me genero un caracter de mas,...
pero si ya comprendi el punto, disculpen, jejeje!

[jordifreek]

Creo que no has entendido el concepto vevni.
No necesito tener una palabra y sustituir una unica letra de dicha palabra por todas las del abecedario (que es lo que hace tu ultima aportacion), lo que necesito es, teniendo una cadena que almacena 5 caracteres (realmente he dicho 5 desde un principio por poner un ejemplo pero como has dicho en alguna ocasion podrian ser mas) generar todas las combinaciones posibles de cadenas utilizando el abecedario. Esto supondria (no he hecho el calculo) millones de combinaciones posibles.

Empece este post con la idea de obtener el concepto de como se podria llevar a cabo esto, y mi primer planteamiento (antes de iniciar el post) incluia ademas del abecedario, numeros y simbolos. He nombrado unicamente el abecedario porque queria resumirlo y porque lo que quiero es eso, entender como hacerlo y poder evolucionarlo con numeros y simbolos.

El algoritmo de cybersersupremo (por cierto le he metido un sleep a 0.5 en cada for y se me sigue colgando el navegador) seria funcional para el planteamiento inicial que he propuesto pero no para este segundo (añadiendo numeros y caracteres) aunque se me ocurre algo declarando primero arrays que contengan las letras, numeros y simbolos....

[jordifreek]

te me adelantes vevni ;)

[vevni]

tarda mas de 1 minuto, casi 2.. yo lo probe con el firefox tengo una extension k marca cuanto tarda en cargar la pag. ami se me muerio al minuto...

pero se cuelga pork hay un error =, genera mas de 5 caracteres.... ami se me colgo en el caracter 7...

[j_aroche]

tambien puedes generarlo con la linea de comandos:

Código:

php script.php > archivo.txt

así no arriegas al frágil FF

[vevni]

cierto, no tiene porque ser en el navegador, buen dato,
oye j_aroche eh estado visitando tu blog, interesantes post tienes, saludos...
ya eh comentado sobre varios, espero revises, jejeje saludos!!

[jordifreek]

No lo habia pensado j_roche, se me habia ocurrido pasar el script a otro lenguage como c#, probaré de ambos modos. Gracias ;)

[Asgaard]

Saludos,

no sé si el tema ya está algo viejo, pero intento aportar mi granito de arena.

Creo que para un número de palabras de longitud "n" la única solución viable es mediante la técnica de recursividad. Os muestro mi código y os comento:

Código PHP:

  $longitud = "2";
$caracteres = array("0","1","2","3","4","5","6","7","8","9",
                    "a","b","c","d","e","f","g","h","i","j",
                    "k","l","m","n","o","p","q","r","s","t",
                    "u","v","w","x","y","z"); 
 
function getCadena($cad,$long)
{
    global $caracteres;
    
    if ($long == "0")
    {
        echo ($cad."\n");
    }
    else
    {
        for ($i=0;$i<count($caracteres);$i++)
        {
            $caracter = $caracteres[$i];
            $aux = $cad.$caracter;
            getCadena($aux,$long-1);
        }
    }
}
 
getCadena("",$longitud); 
   

$longitud es la variable que indica la longitud de la palabra, está puesta a 2 para que no machaque mucho la memoria, podeis pasar la salida a un archivo como se ha dicho antes, etc...

$caracteres indica todo el universo de caracteres que se van a usar, aquí se introducen letras además de números.

getCadena es la función recursiva, a la cual se le pasan dos parámetros, uno la cadena actual de salida, y otro la longitud de las subcadenas restantes.

básicamente es un funcionamiento muy sencillo, para formar una cadena de palabras de 5 caracteres de longitud, debemos usar todas las letras y combinarlo con todas las subcadenas de 4 caracteres de longitud...

De esta manera, la condición de salida será cuando debamos formar subcadenas de 0 caracteres, momento en el cual pintamos por pantalla la palabra formada.

la condición recursiva es sencilla, recorremos todo el array de caracteres posibles, y para cada uno, llamamos a la función getCadena, pero de longitud -1 y con el caracter actual uniéndolo a la cadena.

Probarlo si quereis, yo le he estado haciendo pruebas y funciona bastante bien...

[milo9022]

Código PHP:

  <?php
public function($palabra)
$i=0;
for($u='a'; true; $u++)
{
    $i++;
    if($u==$palabra)
    {
        echo $u.' se encontro en el '.$i.' intento'.'<br>';
        break;
    }
}
echo 'termino el programa';
/*la unica restricion es que si el servidor no recibe respuesta despues de 30 seg
termina el proceso, ademas se puede demorar dependiendo el tamaño de la
palabra
*/
//RESULTADO PARA avion
/*
avion se encontro en el 850136 intento
termino el programa
*/   

[stramin]

Lo que has hecho es un buscador y lo que se pidio en el 2007 era un generador de combinaciones.

Interesante tema por cierto, claro que yo lo habría hecho así:

Código PHP:

  for($w=base_convert("aaaaa",36,10);$w<base_convert("zzzzz",36,10);$w++) if(!preg_match("/\d/",base_convert($w,10,36))) echo "
<div>".base_convert($w,10,36)."</div>"; 
   

(No probar este código sin modificar el "zzzzz" por "bbbbb", de modo que solo muestre las combinaciones entre aaaaa y bbbbb, ya que mostrarlas todas les pegará el servidor)