置换秩算法

Question

我正在努力寻找有效的算法来计算排列的秩，反之亦然（给定排名的排列）。有人可以提供一些建议吗？

Answer 1

你有没有重复元素的数组？

如果有只有独特的元素，以下递归计算X[m:n]秩为长度n-m+1的置换：

秩（X，M：N）= RankOfElement（X [M]，从零开始N）

两个Rank和RankOfElement是（从0开始）： - ：X（M）+排名（X，第（m + 1 N）[m×n个）*阶乘。

基本上，Rank(permutation) = Rank(first permutation starting with first letter of permutation) + Rank(permutation with first letter deleted)，例如，对于字符串EDCBA这意味着Rank(EDCBA) = Rank(EABCD) + Rank(DCBA)。

这可以通过改变第一项被扩展到非唯一案件：

秩（X，M：N）=秩（X，（M + 1）：N）+Σ在（Y∈X [M：N]，Y < X [M]）的组合的数量的{X [M：N]} - {Y}。

Answer 2

编辑

我刚才看到你的评论。漂亮的图形！正确的你想要的是树遍历。

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

所以这意味着你的'等级'有一定的灵活性。你可以定义它。只要在树中顺序遍历所需的任何类型（inorder，preorder，postorder，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) 

如果您从这个组合和基数的角度思考它，即使在更复杂的情况下也不会出错。只要你想要的级别，并将其转换为适合您的字母表的基础。你可能会对Mixed Radix Conversion on Wikipedia, here感兴趣