Asignar un numero natural a una permutacion

patxi
13 de Agosto del 2009
Hola. Me estan surgiendo muchas dudas a la hora de obtener lo siguiente:

Tengo que generar permutaciones de un vector de 9 cifras, permutaciones sin repeticion [1,2,3,4,5,6,7,8,9], [1,3,2,4,5,6,7,8,9], [9,8,7,6,5,4,3,2,1], etc... Hasta ahi todo bien, tengo un algoritmo que es capaz de generar vectores de este tipo aleatoriamente y tambien, se cuantas combinaciones son posibles ya que son 9!. Lo que pasa que tengo que, como el numero de combinaciones es 9! (o sea, 362880) tengo que conseguir un procedimiento que, a la hora de darle un numero natural (que este entre 0 y 362879, como cuento el 0 tambien por eso disminuyo un valor) me asigne una combinacion de los valores del vector, una en particular.

Aqui es donde tengo las dudas y me estoy rompiendo la cabeza. He probado de varias formas aunque de momento sin resultado, una de ellas la cual creia que me iba a ir bien hacia lo siguiente: separaba varios casos segun el numero natural que añadia por ejemplo

entre 0 y 40319 tengo los vectores donde el primer valor es 1 [1,x,x,x,x,x,x,x,x]
entre 40320 y 80639 tengo los vectores donde estaria el primer valor con 2 [2,x,x,x,x,x,x,x,x]

y asi hasta 322560 y 362879 [9,x,x,x,x,x,x,x,x]

la franja, como se puede observar es de 40320, que es 8!, o sea, las posibles combinaciones con los 8 demas valores del vector.

para ir obteniendo los siguientes valores dividia el numero natural que le pasaba al procedimiento entre 9 y hacia lo mismo, establecer otra franja para ir obteniendo los demas valores, lo que seria para lo siguiente

entre 0 y 5039 añadiria el primer valor, supongamos que hemos añadido el 1, pues el primer valor en este caso seria el 2 [1,2,x,x,x,x,x,x,x]

entre el 5040 y 10079 añadiria el segundo valor [1,3,x,x,x,x,x,x,x]

y asi, voy reduciendo hasta llegar al final, lo que pasa es que, por ejemplo
pruebo con el valor 200000 y se obtendria el [5,6,4,7,3,8,2,9,1] y si pruebo con el 200001 tambien se obtiene este vector

No se si esta un poco lioso, he procurado explicarlo lo mejor posible y añadiendo ejemplos para intentar dejarlo mas claro.

Pues lo dicho, quisiera si puede ser posible algo de ayuda.
Tambien he pensado en, por ejemplo utilizar algo de este sistema que me habia planteado, establecer la primera franja, y luego ir generando las combinaciones hasta llegar al numero que le paso al parametro

por ejemplo: para el 200000 se encontraria entre la franja de 161280 a 201599 asi que, asignaria el primer valor del vector [5,x,x,x,x,x,x,x,x]

y empezaria a generar combinaciones, desde la 161280 hasta llegar a la 200000.

Un saludo.

god2710
13 de Agosto del 2009
Si es que necesitas una opcion rapida y no te importa usar un poco de memoria, un poco mucho te diria, lo mas rapido seria cargar cada fila en una matriz y entonces el numero de la fila seria tu numero natural pero creo que tardaria mucho..xD
Porque de 9???jaja

mandolina
13 de Agosto del 2009
Una posible solución seria...

Dado el siguiente conjunto de elementos {5 ,15 ,35 ,50 ,82 ,34 ,12 ,8 ,4}:

ELE POS POS_BIN
5 = 0 = 000
15 = 1 = 001
35 = 2 = 010
50 = 3 = 011
82 = 4 = 100
34 = 5 = 101
12 = 6 = 110
8 = 7 = 111


CONJUNTO POS 9 ELE DECIMAL
000001010011100101110111 1000 5478264

Con lo cual para representar {15,35,82,12,4,5,8,50,34} seria el número

001010100110000111011101 0100 44441044

Aunque si pudieras manejar numeros de longitud mayor de 32 bits la trasformación
seria mas directa a nivel de 4 bits por posición.