Finding the index of a given permutation

Question

I'm reading the numbers 0, 1, ..., (N - 1) one by one in some order. My goal is to find the lexicography index of this given permutation, using only O(1) space.

This question was asked before, but all the algorithms I could find used O(N) space. I'm starting to think that it's not possible. But it would really help me a lot with reducing the number of allocations.

Answer 1

I just wrote a code using Visual Basic and my program can directly calculate every index or every corresponding permutation to a given index up to 17 elements (this limit is due to the approximation of the scientific notation of numbers over 17! of my compiler).

If you are interested I can I can send the program or publish it somewhere for download. It works fine and It can be useful for testing and paragon the output of your codes.

I used the method of James D. McCaffrey called factoradic and you can read about it here and something also here (in the discussion at the end of the page).