Nächste größere Permutation

(26. November 2020)

Permutation von drei verschiedenen Farben

Lassen Sie uns zunächst verstehen, was Permutation bedeutet. Die Definition aus Wikipedia lautet: „ In Mathematik , a Permutation eines set ist im Grunde genommen eine Anordnung seiner Mitglieder in einer Sequenz oder lineare Reihenfolge oder wenn das Set bereits bestellt ist eine Neuordnung seiner Elemente. Das Wort „Permutation“ bezieht sich auch auf den Vorgang oder den Prozess des Änderns der linearen Reihenfolge einer geordneten Menge.

Wie die Definition sagt, bedeutet Permutation also, eine Menge gegebener Objekte in neu anzuordnen alle möglichen Bestellungen. Wie wir im obigen Diagramm sehen können, können drei verschiedene Farben auf 6 Arten angeordnet werden, nämlich {RGB, RBG, GRB, GBR, BRG, BGR}.

Eine mathematische Formel zur Berechnung der Anzahl der möglichen Anordnungen für n verschiedene Objekte ist gegeben durch n!, wobei n! = n * (n-1) * (n-2) *… * 1

s gibt viele Möglichkeiten, systematisch alle Permutationen einer gegebenen Sequenz zu generieren. Ein klassischer Algorithmus basiert darauf, die nächste Permutation in lexikografischer / Wörterbuch- / alphabetischer Reihenfolge zu finden, falls vorhanden.

Die Problemstellung hier lautet also, wir erhalten eine Reihe von Alphabeten, die wir vielleicht können Nennen wir es eine Zeichenfolge, und wir müssen den nächsten lexikografischen Satz von Alphabeten oder die nächste lexikografische größere Zeichenfolge oder die Zeichenfolge finden, die im Wörterbuch als nächstes nach der aktuellen Zeichenfolge mit demselben Satz von Alphabeten wie in der aktuellen Zeichenfolge erscheint.

Nehmen wir ein Beispiel für Zahlen, um es besser zu verstehen.

Number = [4,5,2,6,7,3,1]
Die nächst größere Zahl wird sein = [4,5,2, 7,1,3,6 ]

Brute Force

Das erste, was uns in den Sinn kommt, ist, alle Permutationen der angegebenen Zahl zu finden, und die kleinste dieser Permutationen, die ebenfalls größer als unsere aktuelle Zahl ist, wird unsere Antwort sein. Wie wir oben gesehen haben, gibt es n! Möglichkeiten (n = Anzahl der Ziffern in der Anzahl), wobei alle Ziffern als unterschiedlich betrachtet werden. Wenn wir also weiterhin alle Permutationen für eine bestimmte Zahl finden, dauert die Berechnung O (n!) Zeit. Das ist eine hohe Zeitkomplexität, wenn das n eine große Zahl ist.

Optimierung

Wir müssen uns überlegen, wie wir dies verbessern können. Wenn wir genau beobachten, vielleicht für einen kleineren Satz von Zahlen, sehen wir möglicherweise ein Muster. Versuchen wir es mit ein paar Beispielen:

[2,1,3] = nächstgrößere Zahl ist 231
[1,1,5] = nächstgrößere Zahl ist 151
[2,3 , 5,4] = nächstgrößere Zahl ist 2435
[3,2,1] = wir können aus allen möglichen Permutationen

keine Zahlen bilden, die größer als die aktuelle Zahl sind Beobachtung:

Fall 1: [3,2,1]

Hier bewegen wir uns vom rechten Ende und versuchen, das erste abnehmende Element zu finden, damit wir es durch das ersetzen können Element größer als sich selbst von der rechten Seite.

Fall 1: Das nächst größere Element ist nicht möglich in nicht aufsteigender Reihenfolge

Fall 2: [2,3,5,4]

index = 1, Index für das erste abnehmende Element vom rechten Ende
finden Sie das nächst größere Element größer als 3 in der Tauschen Sie es auf der rechten Seite von i = 1 mit nums [i]
Sortieren Sie nun die verbleibenden Elemente nach i = 1 in aufsteigender Reihenfolge, um das kleinste Element zu erhalten. Wir können die Elemente nach i = 1 einfach umkehren, da sie bereits in nicht aufsteigender Reihenfolge sortiert sind

Diese Grafik zeigt, dass beim Vertauschen von 4 und 5 die Sequenz ab 8, dh 86432, immer noch in nicht aufsteigender Reihenfolge sortiert ist, und es ist ziemlich offensichtlich, dass wir das erste abnehmende Element durch das Element ersetzen, das nur größer als es ist und damit die nicht ansteigende Reihenfolge beibehalten.

Eine weitere Beobachtung, die wir von hier aus machen können, ist, dass wir beim Suchen des nächstgrößeren Elements von Index j = i + 1 nach rechts die Suche bei Index j stoppen können wenn nums [j] kleiner oder gleich nums [i] werden, können Elemente nach diesem Index niemals b e größer als nums [i].

Code-Snippet

Im folgenden Code, falls der nächstgrößere Permutation ist nicht möglich, ich konvertiere es in die kleinstmögliche Permutation

Komplexitätsanalyse

Zeitkomplexität = O (n) { im schlimmsten Fall das erste abnehmende Element zu finden, z [1,5,4,3,2]} + O (n) {um die nächstgrößere Zahl im verbleibenden Unterarray rechts zu finden} + O (1) {um das erste abnehmende Element gegen das nächstgrößere Element auszutauschen} + O (n / 2) {um das Sub-Array von i + 1 nach len umzukehren, um es in aufsteigender Reihenfolge zu sortieren} = O (n)

Da kein zusätzlicher Speicherplatz erforderlich ist, wird kein zusätzlicher Speicherplatz benötigt .
Daher Raumkomplexität: O (1)

anke, dass Sie sich diesem Artikel gewidmet haben. Ich hoffe, Sie finden es hilfreich und erhalten einen klaren Einblick. enn Sie noch Fragen haben, können Sie gerne antworten. Wenn Sie es hilfreich finden, teilen Sie es bitte Ihren Kollegen mit. Ihre Klatschen motivieren mich, mehr solche Blogs zu schreiben! :)