1

ウィキペディアから：

辞書式順序生成

0 ≤ k < n! のすべての数値 k に対して、次のアルゴリズムは、初期シーケンス sj、j = 1、...、n の対応する辞書編集順列を生成します。

function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

この背後にあるロジックは何ですか? それはどのように機能しますか??

4

3 に答える 3

3

n 項目のすべての順列の、次の次元を持つ多次元配列を考えてみましょう。

p[n][n-1][n-2]...[1]

多次元配列は、次元の 1 次元配列に線形化できます。

a[n*(n-1)*(n-2)*...*1]

これは可変基数のようなものです。数値の順に並べると、数字の辞書式順序が得られます。

タプル x[n] = eg を参照するために使用するインデックス(i[n],i[n-1]...,i[0])はsum_j i[j]*(j!)

そのため、部門/mod はタプルから次の位置を回復しています。

タプルの k 番目のインデックスの値は、その右側の次元の積であり、たまたま k! です。

于 2009-09-19T01:50:50.560 に答える
1

a[] = { 1,2,3,4,5,6 } of n = 6; のような初期シーケンスがあるとします。k番目のパーマを生成したい。第1位に1つあれば、5つ生成できます！(ie (n-1)! ) perms 残りの場所。

1 ,.......

次に、1 と 2 を交換すると、再び 5 を生成できます。パーマ。

2 ,.......

したがって、k が与えられているので、k の範囲を見つける必要があります。つまり、k が 225 だとすると、5 はいくつ! k は 245/5 を持っていますか? = 2 したがって、k = 245 の場合、私が生成したい順列では、1 位は間違いなく 3 (つまり a[2]) (2*5! = 240 に行った後の bcoz、1 と 3 を交換します)、私は持つでしょう

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

そのため、アルゴリズムでは k/(n-1) を実行します。最初の繰り返しで。剰余 k = k mod (n-1)! を取得します。これは k の新しい値であり、u は (nj) で同じことを再帰的に実行します! 残りの場所で。

于 2009-10-05T07:12:40.523 に答える