排列序号算法

Question

我正在苦苦寻找一种有效的算法来计算排列的等级，以及反过来给定等级求排列。有人可以给一些指针吗？

- vonPetrushev

---

在这里https://dev59.com/E1_Va4cB1Zd3GeqPT38s#8958309我制作了一个图形，说明了问题，并提供了一种解决方案。如果您查看右侧“相关”问题列表，您会发现很多重复的问题。 - user unknown

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(排列) = Rank(以排列第一个字母开头的第一个排列) + Rank(删除第一个字母后的排列)，例如对于字符串EDCBA，这意味着Rank(EDCBA) = Rank(EABCD) + Rank(DCBA)。

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

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

- ElKamina

Answer 2

编辑

我刚看到你的评论。漂亮的图形！你需要的是一种树遍历。

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

这意味着你的“等级”具有一定的灵活性。你可以定义它。只需选择你想要在树上进行的遍历（中序，前序，后序，DFS，BFS）并给每个叶节点编号，随着你直接通过每个叶节点，编号将递增。

因此，只需选择排列的遍历和排序方式，使其对于您的应用程序最自然或方便即可。如果你不能选择，可以问 /dev/random 应该使用哪种遍历方式。

编辑结束

首先，它必须像基数转换一样被考虑。每个排列都处于某个点（它的等级）。以二进制为例。计算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)

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

- Cris Stringfellow