置换的秩

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个字符的字符串上运行这段代码，对于我的电脑来说太多了，无法处理。

- WhitneyChia

---

看看我的解决方案，它只用了3秒钟来计算一个长度为100,000的字符串的唯一排列 :) - Sawel

嘿，Hammer，我认为你的代码有问题。例如，在“abba”上，这应该返回第2个索引。“aabb”，“abab”，然后在排序列表中的第3个元素将是“abba”。但是你的代码返回6。我认为Bakuriu的代码接近/正确，我正在研究它。 - WhitneyChia

在你的问题中，有些部分提到你想要找到所有排列组合。这是根本不可能的，因为它们太多了。例如，你说“你想要找到这个字符串的所有唯一排列组合。”那么为什么你的函数计算的是排名呢？另外，为什么这个函数被称为find_all而不是rank/permutation_rank之类的名称呢？ - Bakuriu

抱歉，应该是唯一排序排列的等级。 - WhitneyChia

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

关于相同元素的问题：它们发挥作用的关键在于，考虑每个元素与其他元素不同的排列数为(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

- Bakuriu

---

@downvoter 能否解释一下？如果您认为答案不正确，可以提供一个测试用例来说明它的失败之处，或者描述一下为什么您认为这个答案是错误/无用的。 - Bakuriu

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

- pseudo_teetotaler

Answer 3

这是我写的一些Ruby代码，可以完美地实现这个功能。如果你有重复的元素，你需要对它进行修改，并决定如何处理它们。

这段代码利用了一个事实，即如果我们有n个元素，每次选择k个元素，那么每种选择将会出现(n-k)!次。例如，[a,b,c,d] -- 如果我们查看所有的排列，其中(4-1)! = 3!个排列以'a'、'b'、'c'和'd'开头。特别地，前3!个排列以'a'开头，接下来的3!个以'b'开头，依此类推。然后，你可以对剩余的元素进行递归操作。

  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

- Dave