Wie funktioniert dieser „Lexographische Ordnungsgenerierungsalgorithmus“?

Question

aus Wikipedia:

Lexikographische Ordnungsgenerierung

Für jede Zahl k erzeugt der folgende Algorithmus mit 0 ≤ k <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;
 }

Was ist der Logik dahinter? Wie funktioniert es??

Answer 1

Stellen Sie sich vor, Sie haben eine ganze Zahl x und Sie möchten wissen, welche Ziffer an der Hunderterstelle steht.(Z.B.Wenn x=4723, möchten Sie die Antwort 7.) Um dies zu berechnen, dividieren Sie zunächst durch 100 und verwerfen den Bruchteil.(In unserem Beispiel bleibt also 47.) Ermitteln Sie dann den Rest, indem Sie durch 10 dividieren.

Angenommen, Sie möchten den Wert der Ziffer an der Tausenderstelle ermitteln.Um das herauszufinden, dividieren Sie zunächst durch 1000, verwerfen den Bruchteil und ermitteln dann erneut den Rest, wenn Sie durch 10 dividieren.

Im regulären dezimalen Zahlensystem enthält jede Stelle einen von 10 Werten.Sie können beobachten, dass wir in unserer Übung zum Finden von Ziffern zunächst durch die Anzahl der möglichen Kombinationen von Werten an den Stellen rechts von dem Wert dividieren, der uns interessiert (10 * 10 im ersten Beispiel).Dann ermitteln wir den Rest, indem wir durch die Anzahl der möglichen Werte für den Ort dividieren, der uns wichtig ist.Natürlich, alle Orte haben 10 mögliche Werte, also dividieren wir einfach durch 10.

Jetzt, Stellen Sie sich ein Nummerierungssystem vor, bei dem jede Stelle eine unterschiedliche Anzahl von Werten enthält.Unser Platz ganz rechts kann zwei Werte haben, 0 oder 1.Die nächste Stelle kann drei Werte haben, 0, 1 oder 2;und so weiter.In diesem System zählen wir so:

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

Das ist es, was Wrang-Wrang unter einer „Zahl mit variabler Basis“ versteht.

Jetzt können Sie sehen, wie wir die Ziffer an einer Stelle in diesem System berechnen.Um die Zahl ganz rechts zu finden, müssen wir nicht zuerst dividieren, sondern ermitteln den Rest modulo 2, da es in dieser Spalte zwei mögliche Werte für eine Ziffer gibt.Um die nächste Spalte links zu finden, dividieren wir zunächst durch die Anzahl möglicher Kombinationen für Ziffern in den Spalten rechts:Da es nur eine Spalte mit zwei möglichen Ziffern gibt, dividieren wir durch 2.Dann nehmen wir den Rest modulo 3, da es für diese Spalte drei mögliche Werte gibt.Weiter links dividieren wir für die 3. Spalte durch 6 (da die Spalten rechts jeweils 3 und 2 Möglichkeiten haben, was durch Multiplikation 6 ergibt) und nehmen dann den Rest modulo 4, da es in dieser Spalte 4 mögliche Werte gibt.

Werfen wir einen Blick auf die Funktion:

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

factorial beginnt als (n-1)!

    for j= 1 to n- 1 {

Jedes Mal, wenn wir hier ankommen, factorial ist gleich (n-j)!Dies ist seitdem zum ersten Mal offensichtlich j=1 und wir wissen, dass wir initialisiert haben factorial zu (n-1)!Das werden wir später sehen factorial ist tatsächlich immer (n-j)!

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

Hier teilen wir k von factorial (was gleich (n-j) ist!) und werfen den Rest weg, dann nehmen wir den Rest, wenn wir das Ergebnis durch (n+1-j) dividieren.Moment mal, das ganze Geschwätz, mit dem ich angefangen habe, kommt mir langsam bekannt vor!Wir ermitteln gerade den Wert der „Ziffer“ in der n-ten Spalte von links mithilfe unseres „Zahlensystems mit variabler Basis“!

Dieses nächste Bit übernimmt die Reihenfolge der Elemente zwischen den Indizes j Und j + tempj und dreht es nach rechts - d.h.Jedes Element bewegt sich um einen Index nach oben, mit Ausnahme des letzten Elements, das zum Anfang zurückgeht.Es ist wichtig zu wissen, dass alle Zahlen rechts von Position j in der richtigen Reihenfolge sind.Wir reißen praktisch einen von ihnen heraus und schieben den Rest voran, um sie in Ordnung zu halten.Welches wir herausnehmen, hängt davon ab tempj.Wann tempj 0 ist, wählen wir den kleinsten aus (und müssen eigentlich keinen Schubs machen), wann tempj gleich n-j ist, wählen wir den größten aus.

        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;

Als nächstes (n-j)!geteilt durch (n-j) ergibt (n-j-1)!Wenn Sie darüber nachdenken, sollten Sie erkennen, dass dies bedeutet, dass wir wieder am Anfang der Schleife sind und j um eins erhöht hat, factorial wird wieder gleich (n-j) sein!

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

Ich hoffe, das hilft ein wenig!

Answer 2

Denken Sie an ein mehrdimensionales Array, alle Permutationen von n Elementen mit Abmessungen:

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

Jedes mehrdimensionales Array in einen 1D-Array der Dimension linearisiert werden:

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

Es ist wie eine variabler Basiszahl; in der Reihenfolge der numerischen Wert gehen tut Sie lexicographic um sich auf die Ziffern geben.

Der Index, den Sie in ein Tupel x zu verweisen, verwenden Sie [n] = z (i[n],i[n-1]...,i[0]) ist sum_j i[j]*(j!)

So hat die Division / mod wird die nächste Position aus dem Tupel gewonnen wird.

Der Wert des k-ten Index in dem Tupel ist das Produkt der Abmessungen zu ihrem Recht, die sie zufällig k!.

Answer 3

u sagen haben erste Sequenz als [] = {1,2,3,4,5,6} von n = 6; und u wollen kte zul erzeugen. Mit 1 auf Ist Ort, kann u 5 generieren! (D (n-1)!) Perms mit den übrigen Stellen.

1 ,.......  

Dann xchange u 1 und 2 wieder u kann wieder 5 generieren! Perms.

2 ,.......

So ist die Idee k gegeben ist, müssen wir das Ausmaß von k finden. Was ich meine ist: k sagen, ist 225, wie viele 5! ist k haben: 245/5! = 2 Also, wenn k = 245, in der Permutation, die ich erzeugen will, der erste Platz ist definitiv 3 (d a [2]) (bcoz nach 2 * 5 gehen! = 240, ich werde xchange 1 und 3), werde ich

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

das ist, warum in der Algo, u do k / (n-1)! in der ersten Iteration. Und Rest K = k mod erhalten (n-1) !. Dies ist neuen Wert von k und u gehen rekursiv das gleiche mit (n-j) zu tun! an den übrigen Stellen.