algorithm - 排列秩算法

Question

我正在努力寻找计算排列等级的有效算法，反之亦然(给定等级的排列)。有人可以指点一下吗？

Answer 1

数组中是否有重复元素？

如果只有独特的元素，下面的递归计算X[m:n]的等级作为长度n-m+1的排列:

Rank(X, m:n) = RankOfElement(X[m], X[m:n]) * Factorial(n - m) + Rank(X, (m+1):n)

Rank 和 RankOfElement 都是从零开始的(从 0 开始)。

基本上，Rank(permutation) = Rank(以排列的第一个字母开始的第一个排列) + Rank(删除第一个字母的排列)，例如对于字符串 EDCBA，这意味着 Rank(EDCBA) = Rank(EABCD) + Rank(DCBA)。

这可以通过更改第一项扩展到非唯一情况:

Rank(X, m:n) = Rank(X, (m+1):n) + ∑ over (y ∈ X[m:n], y < X[m]) of number of combinations of {X[m:n]}-{y} .