置換秩算法

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感興趣