Quero saber se a tarefa explicada abaixo é até teoricamente possível e, em caso afirmativo, como eu poderia fazer isso.

Você tem um espaço deN elementos (ou seja, todos os números entre0 eN-1.) Vamos examinar o espaço de todas as permutações nesse espaço e chamá-loS. oith membro deS, que pode ser marcadoS[i], é a permutação com o número lexicográficoi.

Por exemplo, seN é 3, entãoS é esta lista de permutações:

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

(Obviamente, quando se olha para uma grandeN, esse espaço se torna muito grande,N! para ser exato.)

Agora eu já seicomo obter a permutação pelo seu número de índicei, e eu já sei como fazer o inverso (obtenha o número lexicográfico de uma determinada permutação.) Mas eu quero algo melhor.

Algumas permutações podem ser enormes por si só. Por exemplo, se você estiver olhandoN=10^20. (O tamanho deS seria(10^20)! que acredito ser o maior número que já mencionei em uma pergunta do Stack Overflow :)

Se você estiver olhando apenas uma permutação aleatória nesse espaço, seria tão grande que você não seria capaz de armazenar tudo no disco rígido, e muito menos calcular cada um dos itens pelo número lexicográfico. O que eu quero é ser capaz de acessar o item nessa permutação e também obter o índice de cada item. Ou seja, dadoN ei para especificar uma permutação, tenha uma função que pegue um número de índice e encontre o número que reside nesse índice, e outra função que pegue um número e encontre em qual índice ele reside. Eu quero fazer isso emO(1), portanto, não preciso armazenar ou iterar sobre cada membro na permutação.

Louco, você diz? Impossível? Isso pode ser. Mas considere o seguinte: uma cifra de bloco, como o AES, é essencialmente uma permutação e quase realiza as tarefas que descrevi acima. O AES possui um tamanho de bloco de 16 bytes, o que significa queN é256^16 que é ao redor10^38. (O tamanho deS, não que isso importe, é impressionante(256^16)!ou ao redor10^85070591730234615865843651857942052838, o que supera meu recorde recente de "maior número mencionado no Stack Overflow" :)

Cada chave de criptografia AES especifica uma única permutação emN=256^16. Essa permutação não pôde ser armazenada inteira no seu computador, porque possui mais membros do que átomos no sistema solar. Mas permite acesso ao item. Ao criptografar dados usando o AES, você está olhando os dados bloco por bloco e para cada bloco (membro derange(N)) você produz o bloco criptografado, do qual o membrorange(N) que está no número de índice do bloco original na permutação. E quando você está descriptografando, está fazendo o contrário (localizando o número de índice de um bloco). Acredito que isso seja feito emO(1), Não tenho certeza, mas, de qualquer forma, é muito rápido.

O problema do uso do AES ou de qualquer outra cifra de bloco é que ele limita a informações muito específicas.N, e provavelmente captura apenas uma fração minúscula das permutações possíveis, enquanto eu quero poder usar qualquerN Eu gosto e acesso ao item em qualquer permutaçãoS[i] que eu gosto.

É possível obterO(1) acesso ao item em uma permutação, dado o tamanhoN e número de permutaçãoi? Se sim, como?

(Se eu tiver sorte o suficiente para obter respostas de código aqui, agradeceria se elas estivessem em Python.)

ATUALIZAR:

Algumas pessoas apontaram o triste fato de que o número de permutação em si seria tão grande, que apenas a leitura do número tornaria a tarefa inviável. Em seguida, gostaria de revisar minha pergunta:Dado acesso aorepresentação fatorádica do número lexicográfico de uma permutação, é possível obter algum item na permutação em O (o menor possível)?