排列的等级

Question

所以有一个问题我无法解决，主要是因为计算能力或缺乏。想知道如何编写这个代码以便我可以在我的计算机上实际运行它。问题的要点是：

假设您有一个 string '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。根据定义，该排列具有rank 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)!再次增加我们的排名。

   我们这样做，直到找到索引jwhere 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