Quiero saber si la tarea que se explica a continuación es incluso teóricamente posible y, de ser así, cómo podría hacerlo.

Te dan un espacio deN elementos (es decir, todos los números entre0 yN-1.) Miremos el espacio de todas las permutaciones en ese espacio, y llamémosloS. losith miembro deS, que se puede marcarS[i], es la permutación con el número lexicográficoi.

Por ejemplo, siN es 3, entoncesS es esta lista de permutaciones:

S[0]: 0, 1, 2
S[1]: 0, 2, 1
S[2]: 1, 0, 2
S[3]: 1, 2, 0
S[4]: 2, 0, 1
S[5]: 2, 1, 0

(Por supuesto, al mirar un granN, este espacio se vuelve muy grande,N! para ser exacto.)

Ahora ya lo secómo obtener la permutación por su número de índicei, y ya sé cómo hacer lo contrario (obtener el número lexicográfico de una permutación dada). Pero quiero algo mejor.

Algunas permutaciones pueden ser enormes por sí mismas. Por ejemplo, si estás mirandoN=10^20. (La talla deS sería(10^20)! que creo que es el número más grande que he mencionado en una pregunta de desbordamiento de pila :)

Si está viendo solo una permutación aleatoria en ese espacio, sería tan grande que no podría almacenar todo en su disco duro, y mucho menos calcular cada uno de los artículos por número lexicográfico. Lo que quiero es poder acceder a los elementos en esa permutación y también obtener el índice de cada elemento. Es decir, dadoN yi para especificar una permutación, tenga una función que tome un número de índice y encuentre el número que reside en ese índice, y otra función que tome un número y encuentre en qué índice reside. Quiero hacer eso enO(1), así que no necesito almacenar o iterar sobre cada miembro en la permutación.

¿Loco, dices? ¿Imposible? Podría ser. Pero considere esto: un cifrado de bloque, como AES, es esencialmente una permutación, y casi cumple las tareas que describí anteriormente. AES tiene un tamaño de bloque de 16 bytes, lo que significa queN es256^16 que esta alrededor10^38. (La talla deS, no es que importe, es un asombroso(256^16)!o alrededor10^85070591730234615865843651857942052838, que supera mi récord reciente de "mayor número mencionado en Stack Overflow" :)

Cada clave de cifrado AES especifica una única permutación enN=256^16. Esa permutación no se pudo almacenar completa en su computadora, porque tiene más miembros que átomos en el sistema solar. Pero, le permite acceder a los elementos. Al encriptar datos usando AES, usted está mirando los datos bloque por bloque, y para cada bloque (miembro derange(N)) emite el bloque cifrado, que el miembro derange(N) eso está en el número de índice del bloque original en la permutación. Y cuando estás descifrando, estás haciendo lo contrario (Encontrar el número de índice de un bloque). Creo que esto se hace enO(1), No estoy seguro, pero en cualquier caso es muy rápido.

El problema con el uso de AES o cualquier otro cifrado de bloque es que lo limita a muy específicoN, y probablemente solo captura una pequeña fracción de las posibles permutaciones, mientras que quiero poder usar cualquierN Me gusta y accedo a elementos en cualquier permutaciónS[i] que me gusta.

¿Es posible obtenerO(1) Acceso a elementos en una permutación, tamaño dadoN y número de permutacióni? ¿Si es así, cómo?

(Si tengo la suerte de obtener respuestas de código aquí, agradecería que estén en Python).

ACTUALIZAR:

Algunas personas señalaron el triste hecho de que el número de permutación en sí sería tan grande, que solo leer el número haría que la tarea no sea factible. Entonces, me gustaría revisar mi pregunta:Acceso dado a larepresentación factoradic del número lexicográfico de una permutación, ¿es posible obtener algún elemento en la permutación en O (lo más pequeño posible)?