Permutation rank

Question

therefore, a question arose that I could not solve, mainly because of computing power or lack. I wonder how to encode this so that I can run it on my computer. The essence of the question is this:

Say you have a string 'xyz'and you want to find all the unique permutations of that string. Then you sort them and find the index 'xyz'from the unique permutations. Which seemed simple enough, but as soon as you got a very long line, my computer gives up. Which mathematical path around this, I would suggest, would lead me to code that can actually work 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 in a string of 100 letters, it is just too much for my computer.

Answer 1

This problem can be easily solved by its first simplification and recursive thinking.

So, first suppose that all elements in the input sequence are unique, then the set of “unique” permutations is just a set of permutations.

Now, to find the rank of a sequence a_1, a_2, a_3, ..., a_nin our set of permutations, we can:

• Sort the sequence to get b_1, b_2, ..., b_n. This permutation, by definition, has a rank 0.

• a_1 b_1. , : a_1, a_2, ..., a_n , a_2, ..., a_n.

• b_1 < a_1, , b_1, a_1, a_2, ..., a_n. , (n-1)! = (n-1)*(n-2)*(n-3)*...*1.

  b_1, ..., b_n. b_2 < a_1, , b_2, . (n-1)! .

  , j b_j == a_j, 2.

:

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

:

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

: , , , (n-1)! - , . n, s_1, ..., s_k s_j c_j , `(n-1)!/(c_1! * c_2! *... * c_k!).

, (n-1)! , c_t , .

:

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

, counts, , .

, :

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

, :

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

Answer 2

, .

s = "cdab". s ( ) "a***", "b***". (* ).

2*3!. , , c, .

"a***" "b***", , 'c'. s = 2*3! + index("dab").

"dab"

:

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

python:

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 3

Ruby , . , ( , ).

This means that if we have n elements, each selection of k elements will be displayed exactly (nk)! time. For example, [a, b, c, d] - if we look at all the permutations, (4-1)! = 3! of these will begin with each of "a", "b", "c" and "d". In particular, the first 3! will start with 'a', the next 3! with b etc. Then you return to the rest of the 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