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

BERNA
12 de Febrero del 2005

Me gustaría saber si me pueden a ayudar a decirme que estructura de datos puedo utilizar para almacenar todas las permutaciones posibles, porque hay un caso de que el tamaño máximo es que sea de 20!, y creo que ninguna estructura te permite guardar tal cantidad. También que algoritmo puedo utilizar para encontrar todas las permutaciones de una palabra, leer en ascii y encontrar los siguientes valores. Gracias