排列的等级

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

这个问题可以先简化再递归思考，很容易解决

所以我们首先假设输入序列中的所有元素都是唯一的，那么 "unique" 个排列的集合就是简单的排列集合。

现在要找到序列 a_1, a_2, a_3, ..., a_n 在其排列集合中的排名，我们可以：

对序列进行排序得到b_1, b_2, ..., b_n。根据定义，此排列的秩为 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

我很确定有一种方法可以避免复制计数字典，但现在我累了所以我将把它作为 reader.

的练习

供参考，最终结果：

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

排列的等级

Rank of a Permutation

python

algorithm

performance

permutation

combinatorics