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

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

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

python algorithm performance permutation combinatorics