Foros del Web » Programación para mayores de 30 ;) » C/C++ »

[SOLUCIONADO] Permutaciones

Estas en el tema de Permutaciones en el foro de C/C++ en Foros del Web. Hola amigos. Hoy no os traigo una duda de código sino de lógica. La cuestión es simple de explicar. Teniendo un conjunto 1,2,3,4 encontrar las ...
  #1 (permalink)  
Antiguo 09/02/2017, 15:03
 
Fecha de Ingreso: junio-2014
Mensajes: 139
Antigüedad: 3 años
Puntos: 1
Permutaciones

Hola amigos. Hoy no os traigo una duda de código sino de lógica. La cuestión es simple de explicar. Teniendo un conjunto 1,2,3,4 encontrar las permutaciones. En éste caso es 4 factorial es decir 24 conjuntos.

He encontrado código en c++ y todo. Pero me gustaría hacerlo por mi mismo para aprender. Y el problema surge cuando sobre papel no encuentro la lógica a seguir.

Parto de
{1,2,3,4} la original
{1,2,4,3} la entiendo 3-4 han intercambiado
{1,3,2,4} toman la original e intercambian 2-3
{1,3,4,2} aquí ya me he perdido jeje, parece que toman la anterior y cambian 2-4, por qué toma la anterior??
{1,4,2,3} toman la segunda? porqué?
{1,4,3,2}
y así el resto
{2,1,3,4} {2,1,4,3} {2,3,1,4} {2,3,4,1} {2,4,1,3} {2,4,3,1} {3,1,2,4} {3,1,4,2} {3,2,1,4} {3,2,4,1} {3,4,1,2} {3,4,2,1} {4,1,2,3} {4,1,3,2} {4,2,1,3} {4,2,3,1} {4,3,1,2} {4,3,2,1}
Se supone que sigue

Alguien que me eche una mano?
  #2 (permalink)  
Antiguo 10/02/2017, 05:06
 
Fecha de Ingreso: junio-2010
Ubicación: Madrid
Mensajes: 607
Antigüedad: 7 años
Puntos: 73
Respuesta: Permutaciones

Se trata de una recursión. Fíjate en las seis primeras variaciones que has puesto:

Fijas el primer número de la lista y, luego, con los otros tres, haces todas las variaciones posibles (en total, 6). Para hacer estas variaciones sobre tres elementos, a su vez, fijas el primero de los tres y haces las variaciones (2) con los dos elementos que quedan.

A continuación, intercambias el primer número con el segundo, y repites el proceso anterior. Y así, con todos los números de la lista.

La recursión empleada es simple:

Con dos elementos, tengo dos variaciones posibles.

Con tres elementos, tengo, para cada elemento, dos variaciones, correspondientes a los otros dos. En total, 3*2=6 variaciones.

Con cuatro elementos, tengo, para cada elemento, las seis variaciones que corresponden a los otros tres, en total, 4*(3*2)=24.

Y así, sucesivamente, hasta que te aburras.

¿El modo de implementarlo en una función? Pasa un arreglo de N elementos. Para cada uno de esos elementos, dentro de la función creas un arreglo de N-1 elementos y vuelves a llamar a la función. Así, hasta que lleguemos a un arreglo de 2 elementos. El escribir la función y cómo guardar las variaciones que vayan saliendo lo dejamos como tarea para este fin de semana, que se anuncia mal tiempo.

Saludos,
  #3 (permalink)  
Antiguo 10/02/2017, 22:16
 
Fecha de Ingreso: junio-2014
Mensajes: 139
Antigüedad: 3 años
Puntos: 1
Respuesta: Permutaciones

Hola muchas gracias!!! Ahora ya lo entiendo, la lógica ya está clara, la implementación si creo que es más complicada porque quiero hacerlo con funciones recursivas como me mencionas, pero voy bien jeje.

Saludos



La zona horaria es GMT -6. Ahora son las 17:56.