順列ランクアルゴリズム

Question

私は、順列のランクを計算するための効率的なアルゴリズムを見つけようとしています。その逆もあります（与えられたランクの順列）。誰かが指針を与えることはできますか？

Answer 1

配列に繰り返し要素がありますか？

のみユニークな要素がある場合は、次の再帰は、長さn-m+1の順列としてX[m:n]のランクを計算する：

ランク（X、M：N）= RankOfElement（X [M]、 X [M：N]）*階乗（N - M）+ランク（X、（M + 1）：N）

両方RankとRankOfElementはゼロベース（0から始まる）です。例えば、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）+Σ {X [m：n]} - {y}の組み合わせの数（y∈X[m：n]、y <×[m]）である。

Answer 2

EDIT

私はちょうどあなたのコメントを見ました。素敵なグラフィック！あなたが望むものは、木が横切ることです。

あなたの順列の各位置がツリー内でどのように異なったレベルになっているかに注目してください。そのツリー内のルートからリーフノードまでのすべてのパスが可能な順列です。

これは、あなたの「ランク」にある程度の柔軟性があることを意味します。あなたはそれを定義するようになる。あなたが各葉ノードをまっすぐ進むにつれて増えた葉ノードの番号付けを与えるために、あなたがツリー（inorder、preorder、postorder、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