Fast permutation -> number -> permutation mapping algorithms
- by ijw
I have n elements. For the sake of an example, let's say, 7 elements, 1234567. I know there are 7! = 5040 permutations possible of these 7 elements.
I want a fast algorithm comprising two functions:
f(number) maps a number between 0 and 5039 to a unique permutation, and
f'(permutation) maps the permutation back to the number that it was generated from.
I don't care about the correspondence between number and permutation, providing each permutation has its own unique number.
So, for instance, I might have functions where
f(0) = '1234567'
f'('1234567') = 0
The fastest algorithm that comes to mind is to enumerate all permutations and create a lookup table in both directions, so that, once the tables are created, f(0) would be O(1) and f('1234567') would be a lookup on a string. However, this is memory hungry, particularly when n becomes large.
Can anyone propose another algorithm that would work quickly and without the memory disadvantage?
