Permutation with Repetition Index Conversion

Question

I'm looking for the equation to determine the index of a permutation with repetition with known parameters.

For example: A total of $9$ values, $4$ A's and $5$ B's Gives a total of $126$ permutations with repetition. $$\frac{9!}{4! \cdot 5!} = 126$$

The Zero-based lexicographical order goes from 0 = AAAABBBBB to 125 = BBBBBAAAA This data set is trivial enough that I just generated all the values with code, but large data sets are impractical. I know that index 76 = BABABABAB since I have a list of answers, but I don't want to generate a partial or a full list.

How do I direclty convert any sequence such as BABABABAB to the permutation with repetition index? How do I direclty do the reverse and convert the permutation with repetition index back to the sequence?

I'm looking for the equations / methods to use in a non-trivial example.

Lexicographical order is prefered, but not required as long as the method can convert in both directions (Sequence => Index and Index => Sequence).

Answer 1

Forward conversion was explained in "Lexicographical rank of a string with duplicate characters". In short, I'm referencing the other answer from that question:

If the $i$th character is repeated $n_i$ times, then the total number of permutations is given by:

$$ \frac{(n_1+n_2+\dots+n_m)!}{n_1!\cdot n_2! \cdot \space ... \space \cdot n_m!} $$

We can at $k$th step consider the $k$th character of the given string and fix all characters before it. Now, if you replace this character with any of the preceding characters, then each of the possible permutations will precede the given permutation.

We can calculate the number of such permutations with the given formula. Summing these calculations over all steps will give the total number of preceding permutations to the given permutation, which is the number we are after.

I've implemented this in python and tested it on your example: (proof of concept)

from math import factorial
from functools import reduce
from collections import Counter

def lexicographical_index(string):
    [rank, l, freqs] = [0, len(string), Counter(string)]
    min_ord = min([ord(key) for key in freqs.keys()])
    for n in range(l):
        fsum = sum([freqs[chr(j)] for j in range(min_ord,ord(string[n]))])
        fprod = reduce(lambda x,y: y*x, [factorial(v) for v in freqs.values()])
        freqs[string[n]] -= 1;
        rank += ((fsum * factorial(l-n-1)) // fprod)
    return rank

print(lexicographical_index("babababab"))

which returns the expected result:

76

and should run in $O(m\cdot n)$ where $m$ is the number of unique chars among the $n$ chars.

The backward conversion uses the same idea. This time around, we are fixing characters from smallest to largest and counting the possible permutations until the count exceeds our index, until we fix (find) every character.

This was additionally explained and implemented in:

• "Find n-th lexicographically permutation of a string | Set 2" from geeksforgeeks.org.

• Algorithm for finding multiset permutation given lexicographic index on StackOverflow.