Rank of a Permutation

Question

so there was a question I wasn't able to solve mainly because of computing power or lack thereof. Was wondering how to code this so that I can actually run it on my computer. The gist of the questions is:

Let's say you have a string 'xyz', and you want to find all unique permutations of this string. Then you sort them and find the index of 'xyz' out of the unique permutations. Which seemed simple enough but then once you get a really long string, my computer gives up. What's the mathematical way around this which I'd assume would lead me to code that can actually run on my laptop.

from itertools import permutations

def find_rank(n):
    perms = [''.join(p) for p in permutations(n)]
    perms = sorted(set(perms))
    loc = perms.index(n)
    return loc

But if I want to run this code on a string that's 100 letters long, it's just way too many for my computer to handle.

Answer 1

Let's see how index of string can be calculated without finding all permutation of the string.

Consider string s = "cdab". Now, before string s (in lexical order), strings "a***", "b***" would be there. (* denotes remaining characters).

That's 2*3! strings. So any strings starting with c will have index more than this.

After "a***" and "b***", string starting with 'c'will begin. Index of the string s = 2*3! + index("dab").

Now recursively find the index for "dab"

Just for illustration, order of string goes as follows :

    a*** --> 3! 
    b*** --> 3!
    ca** --> 2!
    cb** --> 2!
    cdab --> 1  

Following is the python code :

import math

def index(s):
    if(len(s)==1):
        return 1
    first_char = s[0]
    character_greater = 0
    for c in s:
        if(first_char>c):
            character_greater = character_greater+1
    return (character_greater*math.factorial((len(s)-1)) + index(s[1:len(s)])    

Answer 2

This problem can be easily solved by first simplifying it and thinking recursively.

So let's first assume that all the elements in the input sequence are unique, then the set of "unique" permutations is simply the set of permutations.

Now to find the rank of the sequence a_1, a_2, a_3, ..., a_n into its set of permutations we can:

1. Sort the sequence to obtain b_1, b_2, ..., b_n. This permutation by definition has rank 0.

2. Now we compare a_1 and b_1. If they are the same then we can simply remove them from the problem: the rank of a_1, a_2, ..., a_n will be the same as the rank of just a_2, ..., a_n.

3. Otherwise b_1 < a_1, but then all permutations that start with b_1 are going to be smaller than a_1, a_2, ..., a_n. The number of such permutations is easy to compute, it's just (n-1)! = (n-1)*(n-2)*(n-3)*...*1.

   But then we can continue looking at our sequence b_1, ..., b_n. If b_2 < a_1, again all permutations starting with b_2 will be smaller. So we should add (n-1)! again to our rank.

   We do this until we find an index j where b_j == a_j, and then we end up at point 2.

This can be implemented quite easily:

import math

def permutation_rank(seq):
    ref = sorted(seq)
    if ref == seq:
        return 0
    else:
        rank = 0
        f = math.factorial(len(seq)-1)
        for x in ref:
            if x < seq[0]:
                rank += f
            else:
                rank += permutation_rank(seq[1:]) if seq[1:] else 0
                return rank

The solution is pretty fast:

In [24]: import string
    ...: import random
    ...: seq = list(string.ascii_lowercase)
    ...: random.shuffle(seq)
    ...: print(*seq)
    ...: print(permutation_rank(seq))
    ...: 
r q n c d w s k a z b e m g u f i o l t j x p h y v
273956214557578232851005079

On the issue of equal elements: the point where they come into play is that (n-1)! is the number of permutations, considering each element as different from the others. If you have a sequence of length n, made of symbol s_1, ..., s_k and symbol s_j appears c_j times then the number of unique permutations is `(n-1)! / (c_1! * c_2! * ... * c_k!).

This means that instead of just adding (n-1)! we have to divide it by that number, and also we want to decrease by one the count c_t of the current symbol we are considering.

This can be done in this way:

import math
from collections import Counter
from functools import reduce
from operator import mul

def permutation_rank(seq):
    ref = sorted(seq)
    counts = Counter(ref)

    if ref == seq:
        return 0
    else:
        rank = 0
        f = math.factorial(len(seq)-1)
        for x in sorted(set(ref)):
            if x < seq[0]:
                counts_copy = counts.copy()
                counts_copy[x] -= 1
                rank += f//(reduce(mul, (math.factorial(c) for c in counts_copy.values()), 1))
            else:
                rank += permutation_rank(seq[1:]) if seq[1:] else 0
                return rank

I'm pretty sure there is a way to avoid copying the counts dictionary, but right now I'm tired so I'll let that as an exercise for the reader.

For reference, the final result:

In [44]: for i,x in enumerate(sorted(set(it.permutations('aabc')))):
    ...:     print(i, x, permutation_rank(x))
    ...:     
0 ('a', 'a', 'b', 'c') 0
1 ('a', 'a', 'c', 'b') 1
2 ('a', 'b', 'a', 'c') 2
3 ('a', 'b', 'c', 'a') 3
4 ('a', 'c', 'a', 'b') 4
5 ('a', 'c', 'b', 'a') 5
6 ('b', 'a', 'a', 'c') 6
7 ('b', 'a', 'c', 'a') 7
8 ('b', 'c', 'a', 'a') 8
9 ('c', 'a', 'a', 'b') 9
10 ('c', 'a', 'b', 'a') 10
11 ('c', 'b', 'a', 'a') 11

And to show that it is efficient:

In [45]: permutation_rank('zuibibzboofpaoibpaybfyab')
Out[45]: 246218968687554178

Answer 3

Here's some Ruby code I wrote to do exactly this. You'd need to modify it if you have repeated elements (and decide how you want to handle them).

This takes advantage that if we have n elements, each selection of k elements will show up exactly (n-k)! times. E.g., [a,b,c,d] -- if we look at all permutations, (4-1)! = 3! of them will start with each of 'a', 'b', 'c', and 'd'. In particular, the first 3! will start with 'a', the next 3! with b, and so on. Then you recurse on the remaining elts.

  def get_perm_id(arr)
    arr_len = arr.length
    raise "get_perm_id requires an array of unique elts" if arr_len != arr.uniq.length
    arr_sorted = arr.sort
    perm_num = 0
    0.upto(arr_len - 2) do |i|
      arr_elt = self[i]
      sorted_index = arr_sorted.find_index(arr_elt)
      sorted_right_index = arr_sorted.length - sorted_index - 1
      right_index = arr_len - i - 1
      left_delta = [0, right_index - sorted_right_index].max
      perm_num += left_delta * (arr_len - i - 1).factorial
      arr_sorted.slice!(sorted_index)
    end
    perm_num
  end