排列排序算法

Question

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

Answer 1

数组中有重复元素吗？

如果仅存在唯一元素，则以下递归将 X[m:n] 的排名计算为长度 n-m+1 的排列>：

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

两者都是Rank 和 RankOfElement 是从零开始的（从 0 开始）。

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

通过更改第一项，可以将其扩展到非唯一情况：

Rank(X, m:n) = Rank(X, (m+1):n) + Σ over (y ∈ X[m:n], y < X[m]) 的组合数量{X[m:n]}-{y} 。

Answer 2

编辑

我刚刚看到你的评论。不错的图形！你想要的是树遍历。

请注意排列中的每个位置在树中如何具有不同的级别？该树中从根到叶节点的每条路径都是可能的排列。

所以这意味着你的“等级”有一定的灵活性。你得定义它。只需将其设置为您想要对树进行的任何类型的遍历（中序、前序、后序、DFS、BFS）即可为您提供当您直接遍历每个叶节点时递增的叶节点编号。

因此，只需选择您认为对您的应用程序最自然或最方便的排列的遍历和排名即可。如果您无法选择，请询问 /dev/random 您应该使用哪种遍历。

END EDIT

首先，必须将其视为基本转换。每个排列都在一个点（它是排名）。想想二进制。计算 n 个字符上的 2 个字母表排列的有效算法是什么？只需分配排名即可得到排列。

同样的事情也适用于其他大小的字母。显然，如果您的位置具有不同大小的字母表，事情会更加复杂，但您仍然可以进行组合：

total possible = pi(|a|_i) for all i in positions

|a|_i alphabet size at position i

and assuming all |a|_i are equal to b you have

rank of permutation = sigma(b**i * a_i)

a_i is actual alphabet character chosen at position i.

So over the 5 alphabet (ABCDE) 

The rank of AAAAA = 0 (or 1)
The rank of EEEED = 5**6 - 2

然后要从排名中获得排列，只需使用基数公式：我似乎记得：

a_i = (P % b**(i+1) - P & (b**i))/(b**i)

如果您从组合和基数的角度考虑它，即使在更复杂的情况下，你也不会出错。只需采用您想要的任何排名并将其转换为适合您的字母表的基础即可。您可能对维基百科上的混合基数转换感兴趣