Die Methode der Wörterbuchreihenfolge besteht darin, alle Arrangements nacheinander gemäß der Idee des Wörterbuchs zu generieren.
In Mathematik, Wörterbuch- oder Wörterbuchreihenfolge (auch als Vokabular -Ordnung, Wörterbuchreihenfolge, alphabetische Ordnung oder Wörterbuchreihenfolge) ist eine Methode der alphabetischen Ordnung, bei der Wörter alphabetische basierend auf alphabetischer Reihenfolge angeordnet sind. Diese Verallgemeinerung liegt hauptsächlich darin, die Gesamtreihenfolge von Sequenzen (oft als Wörter in Informatik bezeichnet) von Elementen zu definieren, die eine geordnete vollständig geordnete Reihe von Elementen definieren (oft als Alphabet bezeichnet).
Für die Anordnung der Zahlen 1, 2, 3 ... n wird die Abfolge verschiedener Anordnungen durch Vergleich der Sequenz der entsprechenden Zahlen von links nach rechts bestimmt. Zum Beispiel steht für die Anordnung 12354 und 12345 der 5 Zahlen die Anordnung 12345 vor und die Anordnung 12354 im Rücken. Nach dieser Verordnung beträgt der erste unter allen Anordnungen der 5 Zahlen 12345 und der letzte 54321.
Zum Beispiel sind alle Arrangements, die aus 1, 2, 3 von klein bis groß sind,:
123.132.213.231.312.321
Alle Arrangements bestehen aus 1, 2, 3, 4:
1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,,
3124, 3142, 3214, 3241, 3412, 3421,,
4123, 4132, 4213, 4231, 4312, 4321.
Zunächst muss eine Folge von Zeichen im angegebenen Zeichensatz angegeben werden, und auf dieser Grundlage wird jede Anordnung nacheinander erzeugt.
[Beispiel] Zeichensatz {1,2,3}, kleinere Zahlen sind zuerst, so dass die in der Wörterbuchreihenfolge erzeugte vollständige Anordnung: 123, 132, 213, 231, 312, 321 beträgt.
Erzeugen Sie die nächste Permutation bei einer vollständigen Permutation, und die sogenannte nächste ist die Zeichenfolge neben dem nächsten ohne Wörterbuchanordnung. Dies erfordert, dass dieser das gleiche Präfix so lange wie möglich das gleiche Präfix aufweist, dh die Variation ist auf das kürzest mögliche Suffix begrenzt.
Es besteht eine gewisse Beziehung zwischen der letzteren Anordnung und der vorherigen Anordnung. Der Lösungsprozess der letzteren Anordnung lautet wie folgt:
Was ist seine nächste Arrangement, mit Arrangement (p) = 2763541, sortiert nach Dictionary?
2763541 (Finden Sie die letzte positive Reihenfolge 35)
2763541 (finden Sie die letzte Nummer 4 nach 3 und sind größer als 3)
2764531 (Schalter 3, 4 Positionen)
2764135 (invert 5, 3, 1 nach 4)
Das Folgende ist eine Beschreibung der nächsten Anordnung von P [1… n]:
Finde i = max {j | P [j 1] <P [j]} (finde die letzte positive Reihenfolge)
Finden Sie j = max {k | P [i 1] <p [k]} (finde den letzten als P [i 1])
Austausch P [i 1] und P [j], um p [1]… P [I-2] P [J] P [i] P [i+1]… P [J-1] P [I-1] P [J+1]… P [n]
Umkehren Sie die Zahl nach p [j] um P [1]… P [I-2] P [J] P [N]… P [J+1] P [I-1] P [J-1]… P [I]
Die Code -Implementierung ist wie folgt:
private static int [] GetPermutation (int [] in) {int [] ns = in; int base = -1; für (int i = nsgth-1; i> = 1; i--) {if (ns [i-1] <ns [i]) {Base = I-1; Break;}}} // Es wurde zu einem letztem. (int i = nsgth-1; i> = base; i--) {if (ns [i]> ns [base]) {Bigger = i; break;}} // system.out.println (größer); Swap (ns, Base, Bigger); reverse (ns, base+1, nsgth-1); left = i, right = j;while (left < right) {swap(ns, left, right);left++;right--;}}private static void swap(int[] ns, int base, int bigger) {int temp = ns[base];ns[base] = ns[bigger];ns[bigger] = temp;}Zusammenfassen
In der obigen Stelle geht es um die Analyse des Sortieralgorithmus von Java -Sprachwörterbuch und Code. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!