排列的秩

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)])