Finding the ranking of a word (permutations) with duplicate letters

by

Note: this answer is for 1-based rankings, as specified implicitly by example. Here’s some Python that works at least for the two examples provided. The key fact is that suffixperms * ctr[y] // ctr[x] is the number of permutations whose first letter is y of the length-(i + 1) suffix of perm.

from collections import Counter

def rankperm(perm):
    rank = 1
    suffixperms = 1
    ctr = Counter()
    for i in range(len(perm)):
        x = perm[((len(perm) - 1) - i)]
        ctr[x] += 1
        for y in ctr:
            if (y < x):
                rank += ((suffixperms * ctr[y]) // ctr[x])
        suffixperms = ((suffixperms * (i + 1)) // ctr[x])
    return rank
print(rankperm('QUESTION'))
print(rankperm('BOOKKEEPER'))

Java version:

public static long rankPerm(String perm) {
    long rank = 1;
    long suffixPermCount = 1;
    java.util.Map<Character, Integer> charCounts =
        new java.util.HashMap<Character, Integer>();
    for (int i = perm.length() - 1; i > -1; i--) {
        char x = perm.charAt(i);
        int xCount = charCounts.containsKey(x) ? charCounts.get(x) + 1 : 1;
        charCounts.put(x, xCount);
        for (java.util.Map.Entry<Character, Integer> e : charCounts.entrySet()) {
            if (e.getKey() < x) {
                rank += suffixPermCount * e.getValue() / xCount;
            }
        }
        suffixPermCount *= perm.length() - i;
        suffixPermCount /= xCount;
    }
    return rank;
}

Unranking permutations:

from collections import Counter

def unrankperm(letters, rank):
    ctr = Counter()
    permcount = 1
    for i in range(len(letters)):
        x = letters[i]
        ctr[x] += 1
        permcount = (permcount * (i + 1)) // ctr[x]
    # ctr is the histogram of letters
    # permcount is the number of distinct perms of letters
    perm = []
    for i in range(len(letters)):
        for x in sorted(ctr.keys()):
            # suffixcount is the number of distinct perms that begin with x
            suffixcount = permcount * ctr[x] // (len(letters) - i)
            if rank <= suffixcount:
                perm.append(x)
                permcount = suffixcount
                ctr[x] -= 1
                if ctr[x] == 0:
                    del ctr[x]
                break
            rank -= suffixcount
    return ''.join(perm)

More Related Contents:

  1. Ukkonen’s suffix tree algorithm in plain English
  2. How to generate all permutations of a string in PHP?
  3. Algorithm to convert an IEEE 754 double to a string?
  4. Recursively print all permutations of a string (Javascript)
  5. How to generate all the permutations of a multiset?
  6. Are there any better methods to do permutation of string?
  7. Algorithm to find articles with similar text
  8. Print all the permutations of a string in C
  9. Best data structure for implementing a dictionary?
  10. Reverse the ordering of words in a string
  11. Convert Int to String in Swift
  12. How do I remove the file suffix and path portion from a path string in Bash?
  13. In Perl, how can I read an entire file into a string?
  14. Fast algorithm for searching for substrings in a string
  15. Convert string to integer type in Go?
  16. Compare version strings in groovy
  17. Extract numeric part of strings of mixed numbers and characters in R
  18. Similar String algorithm
  19. Use character string as function argument
  20. Find the index of a given permutation in the sorted list of the permutations of a given string
  21. Compare string similarity
  22. Any method equivalent to PadLeft/PadRight?
  23. Delete certain lines in a txt file via a batch file
  24. When using the MOV mnemonic to load/copy a string to a memory register in MASM, are the characters stored in reverse order?
  25. Excel VBA like operator [closed]
  26. Swift – Split string over multiple lines
  27. Groovy String to Date
  28. Finding groups of similar strings in a large set of strings
  29. What is the difference between VBScript’s + and & operator?
  30. counting combinations and permutations efficiently

Leave a Comment