nth lexicographical permutation of string/multiset?

Revision en1, by 0k-, 2020-06-09 20:47:21

I'm curious about a hypothetical problem (I don't know if this appears anywhere): input is a string $$$s$$$ where $$$1 \leq |s| \leq 20$$$ and a number $$$n$$$ where $$$1 \leq n \leq |s|!$$$. Output the $$$nth$$$ lexicographical permutation of $$$s$$$. It is guaranteed that $$$n$$$ will not be larger than the total number of permutations of $$$s$$$.

It's easy to solve this when each character in the string is unique (in general, a set). There's plenty of resources about how to generate the nth permutation of a set. Code snippets like this one that generate a permutation of the range $$$[0,n)$$$ that can be used as the indices for the original string, or the factorial/factoradic number system can be used as in here.

This doesn't work for all strings because it doesn't handle repeated characters. For example with finding the third lexicographic permutation of "aab":

n:   Result:      Actual:
1    012 = abb    011 = abb
2    021 = abb    101 = bab
3    102 = bab    110 = bba

The above approaches fail because they treat the two b characters as different elements, meaning that the resulting permutation abb gets double-counted.

The only resources I can find about strings where characters aren't guaranteed to be unique (in other words, multisets) only talk about finding the next permutation, and if they mention finding the nth permutation it's to calculate the next permutation $$$n$$$ times (or something of equivalent time-complexity), which is obviously too slow outside of tiny strings.

Is there any good approach to solving this sort of problem?

Tags #string, #multiset, #permutation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English 0k- 2020-06-09 20:47:21 1791 Initial revision (published)