この「辞書式順序生成アルゴリズムは、」どのように動作しますか？

Question

からウィキペディアするます：

の辞書式順序生成する

  

すべての数kに対して、0≤K

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;
 }

この背景にあるのロジックのは何ですか？ をどのようにそれが動作しない?? の

Answer 1

あなたは全体の数のxを持っていて、何百もの位置にあるものの数字を知りたい想像してみてください。小数部分を捨て、100によってあなたの最初の除算、これを計算するには（X = 4723場合例えば、あなたは答え7.をしたいです）。あなたは10で割るとき（この例では、これは47のままに）すると、残りを見つけます。

今、あなたは何千もの位置の桁の値を見つけたいとします。あなたは10で割るときは、小数部分を捨て、1000で最初の除算をだろうと確認するには、再度残りを見つけます。

正規小数ナンバリングシステムにおいて、各場所10個のいずれかの値を保持します。あなたは私たち桁見つける運動でそれを観察することができ、我々我々は（最初の例では10 * 10）気に1の右側の場所での値の可能な組み合わせの数によって、最初の除算。我々は気に場所のための可能な値の数で割るときその後、我々は残りの部分を見つけます。もちろん、のすべてのの場所は、10の可能な値を持っているので、我々はわずか10で割るます。

今すぐの、それぞれの場所が異なる値の数を保持しているナンバリングシステムを想像してみてください。私たちの一番右の場所は、2つの値、0または1次の場所には三つの値、0、1または2を持つことができることができます。等々。このシステムでは、我々は次のように数えます：

  0
  1
 10
 11
 20
 21
100
101
110
111
120
121
200
201
210
211
220
...

これはwrang-wrang "は可変塩基価" によって意味するものである。

さて、あなたは私たちは、このシステムの代わりに、数字を計算する方法を見ることができます。一番右を見つけるために、我々は最初に分割する必要はありませんし、その列の数字のための2つの可能な値があるので、我々は、剰余モジュロ2を見つけます。左に次の列を見つけるために、我々は右の列の数字のための可能な組み合わせの数によって、最初の除算：2つの可能な数字と1列のみがありますので、2はその後、我々は残りのモジュロ3を取ることにより、我々は分裂、ので、この列の3つの値があります。我々は6で割る（右の列は6を作るために乗算、3及び2の可能性それぞれを持っているので）、次いで、この列の4つの可能な値があるので、残りのモジュロ4を取る第3列に、左続けます。

の関数を見てみましょう。

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorialは、（N-1）として開始します！

    for j= 1 to n- 1 {

私たちはここに来るたびに、factorialは（N-J）に等しいです！これはj = 1以来、初めてのラウンドは明白であり、我々は我々が（N-1）にfactorialを初期化する知っています！私たちは、後でそのfactorialは（N-j）は、常に実際にある参照してくださいよ！

        tempj:= (k/ factorial) mod (n+ 1- j);

ここでは、我々は（N + 1-J）で結果を分割するときに我々が残っ取る、（！（N-J）に等しい）kによってfactorialを分割し、残りを捨てます。ちょっと待って、私は始めたすべてのことせせらぎは聞き覚えし始めています！私達はちょうど私たちの「可変基数システム」を使用して、左からn番目の欄に「桁」の値を見つけている！

この次のビットはjとj + tempjインデックス間の要素の配列を取得し、右方向に回転させる - すなわち、すべての要素がバック開始に移動最後の一つを除いて、一つの指標を移動させます。これは、位置jの右側のすべての数字が順序であることを認識することが重要です。私たちは、効果的にそれらのいずれかを摘採し、順番にそれらを保つために沿って、残りをナッジしています。私たちが出て摘み取るどちらtempjに依存します。 tempjが0であるとき、私たちは、最小を選ぶ（そして実際にナッジを行う必要はありません）、tempjは、n-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;

次に、（N-J）！ （N-J）（N-J-1）を与えるで割りました！ あなたはそれについて考える場合は、これは我々がループとjの先頭に戻ったときに、1ずつ増加していることを意味していることを確認する必要がありますfactorial再び等しい（N-J）！

        factorial:= factorial/ (n- j);
    }
    return s;
}

私は少しのに役立ちます願っています！

Answer 2

の寸法を有するn個の項目のすべての順列の多次元配列、考える：

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

任意の多次元配列は、次元の1Dアレイに線形化することができます

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

これは、可変ベース番号のようなものです。数値の順に行くと、あなたの数字上の辞書式順序を与えています。

は、タプルxに言及するために使用するインデックス[N] =例えば(i[n],i[n-1]...,i[0])がsum_j i[j]*(j!)である

そこで、分割/ MODは、タプルから次の位置を回復している。

タプルのk番目のインデックスの値がKであることを起こる、その右への寸法の積です。

Answer 3

UはN = 6の[] = {1,2,3,4,5,6}のように初期の配列を有すると言います。 uはk番目のパーマを生成したいです。 イスト場所の1で、Uは5を生成することができます！ （すなわち、（N-1）！）の残りの場所とパーマ。

1 ,.......  

そして、uが1と2をXCHANGEと再びuが再び5を生成することができます！パーマます。

2 ,.......

だから、アイデアをkを与えている

、我々は、kの範囲を見つける必要があります。私は何を意味することは次のとおりです。 どのように多くの5、kは225であると言います！ kは持っているん：5分の245！ = 2 だから、= 245、kは、私が生成する順列では、最初の場所は間違いである場合 3（すなわち、[2]）（bcoz 2 * 5！= 240起こった後、私は1 XCHANGEし、3）、Iがあります

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.)

ALGOで、uは/ Kない理由です（N-1）！最初の反復インチ そして残りのK = KのMOD（N-1）を得ました！これは、kの新しい値であり、uが再帰的に（N-J）と同じことをやって行きます！残りの場所でます。