Bienvenido a Preguntas omegaUp, donde puedes realizar preguntas y recibir respuestas de otros miembros de la comunidad.

Categorías

–2 votos

Hay algún algoritmo/tema de estudio (por ejemplo recursividad, programacion dinamica, combinatoria) para poder realizar todas las permutaciones posibles entre ciertos datos? Ejemplo: todas las cadenas posibles con las letras a c e, serian:
ace, aec, eac, eca, cea, cae.

por Leandro-Leguizamon (280 puntos)
editado por lhchavez

1 Respuesta

0 votos

Empecemos pensando cómo lo harías con papel y lápiz. Cambiaré un poco el orden del ejemplo que pusiste para que esté en orden alfabético y sea más claro el ejemplo:

ace
aec
cea
cae
eac
eca

Se puede observar que hay tres grupos de dos órdenes que siguen el mismo patrón: una letra, seguida de las dos letras restantes en orden alfabético, y luego en orden opuesto. De hecho eso último es equivalente a obtener todas las combinaciones de las letras c y e:

ce
ec

Formalizando un poco, todas las permutaciones de una cadena tienen la forma:

una de las letras + (todas las permutaciones de las letras sobrantes)

intenta convertir eso en un algoritmo en tu lenguaje de programación favorito.

por lhchavez (34.8k puntos)
Si eso lo se, el tema es como prorgamarlo y para distintos caso. Yendo a algo mas especifico de mi problema y complejo. Si tengo 11 numeros distintos, y quiero realizar todas las combinaciones posibles con 6 numeros.
La cantidad sería 11x10x9x8x7x6=332.640 combinaciones posibles. Pero a mi me interesa ver cada combinación.
Algún documento o sitio donde pueda estudiar eso? He investigado y es un tema debatido sin desenlace en muchos foros.
hmmm me extraña que se haya discutido sin desenlace, porque es uno  de los primeros algoritmos que te enseñan cuando se ve el tema de recursión en la escuela. tienes los enlaces a dichos foros?

programarlo es sencillo, estructurando un poco más la prosa que mencioné arriba y convirtiéndolo a pseudocódigo:

    permutaciones(cadena c):
        lista de permutaciones l inicia vacía
        para letra_i en cadena c:
          crea una cadena c' a partir de la cadena c, pero quitando letra_i
          para cada p en permutaciones(c'):
            agrega letra_i + p a la lista l
      regresa la lista l

intenta convertir eso en código y avisa si hay algún paso que no esté suficientemente claro.
Si entiendo, muchas gracias.
Éste es uno de los foros donde leí: http://www.forosdelweb.com/f18/generar-todas-las-combinaciones-posibles-544154/
Uy, ese foro es medio... de dudosa calidad (no tengo nada en contra de PHP, pero típicamente los snippets de código en PHP son... malos). Haciendo la búsqueda con el término correcto en Google (permutaciones, en vez de combinaciones), regresó varios enlaces útiles donde viene incluso código y un enlace a un libro (Matemáticas Discretas): https://www.google.com.mx/search?q=generar%20permutaciones
...