Berna
12 de Febrero del 2005

V. PERMUTACIONES

Descripción
Considera un conjunto de n diferentes elementos que pueden ser permutadas en n! formas diferentes. Tales permutaciones pueden ser ordenadas lexicográficamente y son numeradas con base en este ordenamiento. Por ejemplo, el conjunto {a,b,c} tiene seis posibles permutaciones que pueden ser ordenadas como se muestra a continuación:

1 - abc

2 - acb

...

6 - cba

Entrada
Escribe un programa que pueda calcular la k-esima permutación de un conjunto de n elementos en menos de 1 minuto. Un conjunto estará integrado a partir de un caracter inicial c y los n-1 caracteres ASCII que le siguen. El programa deberá leer un archivo de texto donde cada línea es de la siguiente forma:

k n c

donde k y n son números enteros: 1<=n<=20, 1<=k<=n!
y c es un carácter ASCII.
Archivo: problema5.in

1 3 a

2 3 a

6 3 A

1 4 a

1 4 C

24 4 1

1 20 a

Salida
Para cada línea del archivo de entrada, se dará la permutación correspondiente.
Archivo: problema5.out

abc

acb

CBA

abcd

CDEF

4321

abcdefghijklmnopqrst

Me gustaria saber que estructura de datos me recomiendan para guardar todas las permutaciones posibles porque lo que yo sé, es que ninguna estructura te permite guardar una cantidad de 20!, y ese es uno de los posibles casos que te da el problema. También que puedo hacer para leer en ascii ese valor y como hacerle para leer los siguientes valores ascii. Tambien si me pueden ayudar en el algoritmo para sacar las permutaciones posibles, y como ponerlas en el orden adecuado.