Eu tenho n elementos. Por exemplo, digamos, 7 elementos, 1234567. Sei que existem 7! = 5040 permutações possíveis destes 7 elementos.

Eu quero um algoritmo rápido composto por duas funções:

f (número) mapeia um número entre 0 e 5039 para uma permutação única e

f '(permutação) mapeia a permutação de volta para o número do qual ela foi gerada.

Eu não me importo com a correspondência entre número e permutação, desde que cada permutação tenha seu próprio número único.

Então, por exemplo, eu posso ter funções onde

f(0) = '1234567'
f'('1234567') = 0

O algoritmo mais rápido que vem à mente é enumerar todas as permutações e criar uma tabela de consulta em ambas as direções, de modo que, uma vez criadas as tabelas, f (0) seria O (1) e f ('1234567') seria um pesquisa em uma string. No entanto, isso é fome de memória, especialmente quando n se torna grande.

Alguém pode propor outro algoritmo que funcione rapidamente e sem a desvantagem da memória?