Rank of a Permutation
<p>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:</p>

<p>Let's say you have a string <code>'xyz'</code>, and you want to find all unique permutations of this string. Then you sort them and find the index of <code>'xyz'</code> 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.</p>

<pre><code>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
</code></pre>

<p>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. </p>

<p>This problem can be easily solved by first simplifying it and thinking recursively.</p>

<p>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.</p>

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

<ol>
<li><p>Sort the sequence to obtain <code>b_1, b_2, ..., b_n</code>. This permutation by definition has rank <code>0</code>.</p></li>
<li><p>Now we compare <code>a_1</code> and <code>b_1</code>. If they are the same then we can simply remove them from the problem: the rank of <code>a_1, a_2, ..., a_n</code> will be the same as the rank of just <code>a_2, ..., a_n</code>.</p></li>
<li><p>Otherwise <code>b_1 &lt; a_1</code>, but then <strong>all</strong> permutations that start with <code>b_1</code> are going to be smaller than <code>a_1, a_2, ..., a_n</code>. The number of such permutations is easy to compute, it's just <code>(n-1)! = (n-1)*(n-2)*(n-3)*...*1</code>.</p>

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

<p>We do this until we find an index <code>j</code> where <code>b_j == a_j</code>, and then we end up at point 2.</p></li>
</ol>

<p>This can be implemented quite easily:</p>

<pre><code>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 &lt; seq[0]:
                rank += f
            else:
                rank += permutation_rank(seq[1:]) if seq[1:] else 0
                return rank
</code></pre>

<p>The solution is pretty fast:</p>

<pre><code>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
</code></pre>

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

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

<p>This can be done in this way:</p>

<pre><code>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 &lt; 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
</code></pre>

<p>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.</p>

<p>For reference, the final result:</p>

<pre><code>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
</code></pre>

<p>And to show that it is efficient:</p>

<pre><code>In [45]: permutation_rank('zuibibzboofpaoibpaybfyab')
Out[45]: 246218968687554178
</code></pre>

python algorithm performance permutation combinatorics