Search code examples
c++indexingelementlexicographic

Efficiently calculate index of specific element in lexicographical ordering

I have four elements:

A B C D

I can arrange all permutations of n elements in lexicographical ordering, so for n=2:

0=AA 1=AB 2=AC 3=AD ... 15=DD

How can I, without resorting to counting, calculate the index in this ordering for a specific element?

When I enumerate my elements 0=A 1=B 2=C 3=D and have a string string I can calculate the index like this for n=2

4 * val(string[0]) + val(string[1])
string="AC" -> 4*0 + 2 = 2
string="DD" -> 4*3 + 3 = 15

How can I find the index for any string and n > 2? I only really need it for n=2,3,4,5, but it feels like there should be a general solution that I am not seeing?

Solution

  • Isn't it just

    (4 ^ (n - 1)) * val(string[0])
+ (4 ^ (n - 2)) * val(string[1])
+ ...
+ (4 ^ (0)) * val(string[n-1])

    You'd probably program that with a loop.