Return to Blog

Solving the Permutation Rank problem using Python

By John Lekberg on March 04, 2020.

This week's post is about solving an interview problem: the "Permutation Rank" problem. You will learn:

Problem statement

Consider all permutations of the string "ERDOS". (E.g. "DESRO" is a permutation.) Order the permutations lexicographically, beginning with "DEORS" and ending with "SROED". What is the position of "ERDOS"? ("DEORS" is at position 1.)

A brute force solution

A brute force solution of the "Permutation Rank" problem will:

"ERDOS" has 5 characters, so there 120 (5!) permutations. 120 permutations is a small enough state space that the brute force algorithm is feasible. Here's a Python implementation:

import itertools

def permutation_position_brute_force(word):
    ordered_perms = itertools.permutations(sorted(word))
    goal_perm = tuple(word)
    for position, perm in enumerate(ordered_perms, start=1):
        if perm == goal_perm:
            return position

permutation_position_brute_force("ERDOS")

37

This code uses the built-in function sorted to generate the first permutation in the lexicographic ordering:

sorted("ERDOS")

['D', 'E', 'O', 'R', 'S']

(Don't worry that sorted returns a list and not a string. This won't be a problem for the algorithm.)

Then, itertools.permutations generates all permutations:

list(itertools.permutations(sorted("ERDOS")))

[('D', 'E', 'O', 'R', 'S'),
 ('D', 'E', 'O', 'S', 'R'),
 ('D', 'E', 'R', 'O', 'S'),
 ('D', 'E', 'R', 'S', 'O'),
 ...
 ('S', 'R', 'E', 'O', 'D'),
 ('S', 'R', 'O', 'D', 'E'),
 ('S', 'R', 'O', 'E', 'D')]

If the input is sorted, then itertools.permutations will generate the permutation tuples in lexicographic order. (Read the documentation of itertools.permutations for more information.)

itertools.permutations generates tuples like ('D', 'E', 'O', 'R', 'S') instead of strings like 'DEORS'. I have two ways to deal with this:

I choose to turn the goal string, word, into a goal tuple, goal_perm, because that uses fewer operations.

I use enumerate to associate a position with each permutation, starting at position 1.

How well does the brute force solution scale to larger strings with unique characters?

So the time complexity of permutation_position_brute_force is

O(n!)

This means that if running permutation_position_brute_force on a 10-character word took 1 second, then running the algorithm on a 20-character word would take over 21,000 years! There's got to be a quicker way to solve this.

Counting the number of permutations before the goal

The brute force algorithms counts how many permutations appear before the goal permutation by counting each permutation, one by one. But there is a way to count how many permutations appear before the goal permutation without counting permutations one-by-one.

Here are patterns of the permutations that come before ERDOS:

Because all the patterns are mutually exclusive, I can sum their counts to get the total number of permutations before ERDOS:

24 + 6 + 6 = 36

There are 36 permutations before ERDOS, so ERDOS is at position 37.

How do I know that the three patterns D****, ED***, and EO*** are the only three patterns of permutations before ERDOS?

Here's a Python function, permutation_position_quick, that implements the above procedure:

import math

def permutation_position_quick(word):
    N = len(word)
    
    first = sorted(word)
    
    chars_before = {
        first[i]: first[:i]
        for i in range(N)
    }
    
    count = 0
    for i in range(N):
        possible_chars = set(chars_before[word[i]])
        possible_chars.difference_update(word[:i])
        n_wildcards = N - (i + 1)
           
        count += (
          len(possible_chars) * math.factorial(n_wildcards)
        )
    
    return 1 + count

permutation_position_quick("ERDOS")

37

permutation_position_quick uses set objects to easily remove patterns that would reuse already chosen characters (e.g. invalid patterns like EE***).

I confirm that permutation_position_quick produces the same results as permutation_position_brute_force:

p1 = permutation_position_quick
p2 = permutation_position_brute_force
all(
    p1(word) == p2(word)
    for word in itertools.permutations("ERDOS")
)

True

What is the time complexity of permutation_position_quick?

Because there are O(n) loop iterations and each iteration takes O(n) operations, the overall time complexity of permutation_position_quick is

O(n2)

This means that if running permutation_position_quick on a 10-character word took 1 second, then running the algorithm on a 20-character word would take 4 seconds. (Compare this with permutation_position_brute_force taking over 21,000 years.)

In conclusion...

In this post you learned how to use combinatorics to efficiently solve the "Permutation Rank" problem. The key idea is that you don't need to count every permutation one-by-one. To learn more about combinatorics, check out these documents:

My challenge to you:

This post covered solving the "Permutation Rank" problem for words with unique characters, like "ERDOS". How would you solve the "Permutation Rank" problem for words with duplicated characters, like "TERRENCE"?

If you enjoyed this post, let me know. Share this with your friends and stay tuned for next week's post. See you then!

(If you spot any errors or typos on this post, contact me via my contact page.)