Finding nth permutation in dictionary order with repeats

Question

Given a set of symbols (e.g. $(A, A, B, B, B, C, D, D)$), calculate the nth permutation sorted in alphabetical order. I know how to do this with a set of symbols containing no repeats, but I can't work out how to do it with repeated elements.

Answer 1

Obviously you can't apply the rule for the $n$th permutation of unique objects in a cookbook fashion. Instead, go back to first principles.

The number of permutations that start with $A$ is just the number of permutations of $(A, B, B, B, C, D, D)$. The number of permutations that start with $B$ is just the number of permutations of $(A, A, B, B, C, D, D)$, and so forth.

Let $Px$ be the number of permutations that start with the subsequence $x.$ The two numbers in the previous paragraph are $P(A)$ and $P(B).$ But $P(A, A)$ is the number of permutations starting with $A,A,$ which is the number of permutations of $(B, B, B, C, D, D),$ and $P(A, B)$ is the number of permutations starting with $A,B.$

To find the first letter, start adding up $P(A),$ $P(B),$ and so forth until the cumulative sum is at least $n.$

Supposed this shows the first letter is $C.$ Now, starting with $P(A) + P(B)$ (the number of permutations starting with subsequences earlier than $(C)$,) add $P(B,A),$ $P(B,B),$ and so forth to the total until you have at least $n.$ The point where you stop tells you your second letter.

Unfortunately, $P(A,A) \neq P(A,B),$ for example, so you can't divide $n$ by the number of permutations of seven of the letters to find the first letter. The number of permutations of seven letters depends on which seven letters they are, which depends on what letter was removed from the set. There may be a way to make the calculations more convenient than the procedure I laid out above, but it's not obvious to me.