字句索引で与えられた数値順列を求めるアルゴリズム

Question

数字の集合（例えば1 2 3）とインデックス（例えば2）を与えたアルゴリズムを探しています。レキシコグラフィーの順序。たとえば、この場合、アルゴリズムは1 3 2を返します。

Answer 1

は単純な解決である：

from math import factorial # python math library 

i = 5    # i is the lexicographic index (counting starts from 0) 
n = 3    # n is the length of the permutation 
p = range(1, n + 1) # p is a list from 1 to n 

for k in range(1, n + 1): # k goes from 1 to n 
    f = factorial(n - k) # compute factorial once per iteration 
    d = i // f   # use integer division (like division + floor) 
    print(p[d]),   # print permuted number with trailing space 
    p.remove(p[d])  # delete p[d] from p 
    i = i % f    # reduce i to its remainder 

出力：

3 2 1 

時間複雑性は、Oある（N^2）pであればリストであり、O（N ）pがハッシュテーブルで、factorialがあらかじめ計算されている場合は償却されます。ここで

Answer 2

あなたが使用する言語を指定していないので、here's an implementation in pythonです。

シーケンスのn番目の要素を取得するだけで済みます。

アルゴリズムの考え方の1つは、入力シーケンスのデカルト積を表すシーケンスを生成し、反復する要素をスキップして反復することです。

これは最速の方法ではないかもしれませんが、間違いなく簡単です。速い人はサイボーグの答えを見てください。ここ

Answer 3

は、私は詳細に説明しますScalaではサンプル溶液、次のとおりです。

/** 
    example: index:=15, list:=(1, 2, 3, 4) 
*/ 
def permutationIndex (index: Int, list: List [Int]) : List [Int] = 
    if (list.isEmpty) list else { 
    val len = list.size  // len = 4 
    val max = fac (len)  // max = 24 
    val divisor = max/len // divisor = 6 
    val i = index/divisor // i = 2 
    val el = list (i) 
    el :: permutationIndex (index - divisor * i, list.filter (_ != el)) } 

Scalaはそのあまり知られていないので、私はある、私はアルゴリズムの最後の行を説明する必要があると思いますそれ以外は、かなり自明です。

el :: elist 

は、要素elとリストelistから新しいリストを構成します。 Elistは再帰呼び出しです。

list.filter (_ != el) 

は要素elなしの単なるリストです。

テストも徹底的に小さなリストと：

(0 to fac (4) - 1).map (permutationIndex (_, List (1, 2, 3, 4))).mkString ("\n") 

テスト2例との大きなリストのスピード：

scala> permutationIndex (123456789, (1 to 12).toList) 
res45: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 6, 9, 3) 

scala> permutationIndex (123456790, (1 to 12).toList) 
res46: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6) 

結果は、5歳のラップトップ上ですぐに表示されます。 12要素のListには479 001 600個の置換がありますが、要素が100または1000の場合、このソリューションはまだ高速に動作するはずです.BigIntをIndexとして使用するだけです。

どのように動作しますか？私は、例を視覚化するために、一覧のグラフィックを作った（1、2、3、4）、15のインデックス：

4つの要素のリスト4を生成します！順列（= 24）。

すべての並べ替えをツリー内で視覚化することができます。最初のノードは1..4です。私たちは4を分けます！すべての第1ノードが6つのサブツリーにつながることがわかります。インデックス15を6で割ると、結果は2になり、インデックス2を持つゼロベースリストの値は3になります。したがって、最初のノードは3であり、リストの残りは（1,2,4） 。ここでは/配列/リストのインデックス2を持つ要素にどのように15本のリード線を示し、表が何であれ：

0 1 2 3 4 5 | 6 ... 11 | 12 13 14 15 16 17 | 18 ... 23 
    0  |  1 |   2   |  3 
      |   | 0 1 2 3 4 5 | 

我々は今、12を引く、のためのセルの最初の要素（12 ... 17）最後の3つの要素は、6つの可能な順列を持ち、どのように15が3にマップされるかを見てください。3は配列インデックス1になり、これは要素2であったため、これまでの結果はList（3,2、...） 。

     | 0 1 | 2 3 | 4 5 | 
         | 0 | 1 | 3 | 
           | 0 1 | 

再び、我々は2を減算し、2個の置換、及びインデックス（0,3）との2つの残りの要素で終わり、値へのマッピング（1、4）。私たちは、2番目の要素は、上から15に属する、3の評価にマップすることを、見て、最後のステップのための残りの要素は、他のいずれかです。

       | 0 | 1 | 
          | 0 | 3 | 
          | 3 | 0 | 

私たちの結果は（3、2、4一覧です、1）または索引（2、1、3、0）を指定します。すべてのインデックスを順にテストすると、すべての順列が順番に返されます。言及した記事への

Answer 4

リンク：  http://penguin.ewu.edu/~trolfe/#Shuffle

/* Converting permutation index into a permutation 
* From code accompanying "Algorithm Alley: Randomized Shuffling", 
* Dr. Dobb’s Journal, Vol. 25, No. 1 (January 2000) 
* http://penguin.ewu.edu/~trolfe/#Shuffle 
* 
* Author: Tim Rolfe 
*   RolfeT@earthlink.net 
*   http://penguin.ewu.edu/~trolfe/ 
*/ 
#include <stdio.h> 
#include <stdlib.h> 

// http://stackoverflow.com/questions/8940470/algorithm-for-finding-numerical-permutation-given-lexicographic-index 

// Invert the permutation index --- generate what would be 
// the subscripts in the N-dimensional array with dimensions 
// [N][N-1][N-2]...[2][1] 
void IndexInvert(int J[], int N, int Idx) 
{ int M, K; 

    for (M=1, K=N-1; K > 1; K--) // Generate (N-1)! 
     M *= K; 
    for (K = 0; M > 1; K++) 
    { J[K] = Idx/M; // Offset in dimension K 
     Idx = Idx % M; // Remove K contribution 
     M /= --N;   // next lower factorial 
    } 
    J[K] = Idx;   // Right-most index 
} 

// Generate a permutation based on its index/subscript set. 
// To generate the lexicographic order, this involves _shifting_ 
// characters around rather than swapping. Right-hand side must 
// remain in lexicographic order 
void Permute (char Line[], char first, int N, int Jdx[]) 
{ int Limit; 

    Line[0] = first; 
    for (Limit = 1; Limit < N; Limit++) 
     Line[Limit] = (char)(1+Line[Limit-1]); 

    for (Limit = 0; Limit < N; Limit++) 
    { char Hold; 
     int Idx = Limit + Jdx[Limit]; 
     Hold = Line[Idx]; 
     while (Idx > Limit) 
     { Line[Idx] = Line[Idx-1]; 
     Idx--; 
     } 
     Line[Idx] = Hold; 
    } 
} 

// Note: hard-coded to generate permutation in the set [abc... 
int main(int argc, char** argv) 
{ int N = argc > 1 ? atoi(argv[1]) : 4; 
    char *Perm = (char*) calloc(N+1, sizeof *Perm); 
    int *Jdx = (int*) calloc(N, sizeof *Jdx); 
    int Index = argc > 2 ? atoi(argv[2]) : 23; 
    int K, Validate; 

    for (K = Validate = 1; K <= N; K++) 
     Validate *= K; 
    if (Index < 0 || Index >= Validate) 
    { printf("Invalid index %d: %d! is %d\n", Index, N, Validate); 
     return -1; // Error return 
    } 
    IndexInvert(Jdx, N, Index); 
    Permute (Perm, 'a', N, Jdx); 
    printf("For N = %d, permutation %d in [0..%d] is %s\n", 
      N, Index, Validate-1, Perm); 
    return 0;  // Success return 
}