排列的秩

Question

所以有一個問題，我無法解決，主要是因爲計算能力或缺乏。想知道如何編碼，以便我可以在我的電腦上運行它。問題的要點是：

比方說，你有一個字符串'xyz'，你想找到這個字符串的所有獨特的排列。然後你對它們進行排序，並找出排列中唯一排列的索引'xyz'。這似乎很簡單，但一旦你得到一個非常長的字符串，我的電腦就放棄了。我認爲這種數學方式會導致我的代碼能夠在我的筆記本電腦上運行。

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 

但是，如果我想在一個字符串的100個字母長運行這段代碼，它只是太多的我的電腦來處理。

Answer 1

這個問題可以簡單地通過簡化它並遞歸地思考來解決。因此，我們首先假設輸入序列中的所有元素都是唯一的，那麼「唯一」置換的集合就是排列的集合。

我們找到序列a_1, a_2, a_3, ..., a_n的排名進入其排列集合，我們可以的：

1. 排序的序列，以獲得b_1, b_2, ..., b_n。這個定義的排列有排名0。

2. 現在我們比較a_1和b_1。如果它們相同，那麼我們可以簡單地將它們從問題中移除：a_1, a_2, ..., a_n的排名將與僅僅a_2, ..., a_n的排名相同。

3. 否則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 

在等元素的問題上：t嘿發揮作用是(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 

我敢肯定有一種方法，以避免拷貝數的字典，但現在我已經厭倦了，所以我會告知爲：

這可以通過這種方式來完成爲讀者鍛鍊。

僅供參考，最終的結果是：

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

下面是一些Ruby代碼我寫信給做的正是這一點。如果您有重複的元素（並決定如何處理它們），則需要對其進行修改。

這樣做的好處是，如果我們有n個元素，k個元素的每個選擇都會精確地顯示出來（n-k）！倍。例如[a，b，c，d] - 如果我們看看所有的排列，（4-1）！ = 3！他們將從'a'，'b'，'c'和'd'中的每一個開始。特別是前3！將以'a'開始，接下來的3！與b，等等。然後你遞歸剩下的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 

Answer 3

讓我們來看看如何進行字符串的索引可以沒有找到該字符串的所有排列計算。

考慮串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)])