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><strong>Let's see how index of string can be calculated without finding all permutation of the string.</strong> </p>

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

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

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

<p>Now recursively find the index for <code>"dab"</code></p>

<p>Just for illustration, order of string goes as follows :   </p>

<pre><code>    a*** --&gt; 3! 
    b*** --&gt; 3!
    ca** --&gt; 2!
    cb** --&gt; 2!
    cdab --&gt; 1  
</code></pre>

<p>Following is the python code : </p>

<pre><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&gt;c):
            character_greater = character_greater+1
    return (character_greater*math.factorial((len(s)-1)) + index(s[1:len(s)])    
</code></pre>

python algorithm performance permutation combinatorics