Algorithmus: So finden Sie die nächste lexikografische Permutation

Wenn Sie kurz die lexikografische Reihenfolge beschreiben, erfolgt die Sortierung in alphabetischer Reihenfolge. Das heißt, Die Zeichenfolge - AAA → AAB → AAC → AAD → ……… → WWW - ist in alphabetischer (oder in unserem Fall lexikografischer) Reihenfolge sortiert.

Stellen Sie sich vor, Sie haben eine endliche Folge von Zeichen, z. B. 0, 1, 2, 5, 3, 3, 0, und Sie müssen alle möglichen Permutationen dieser Zeichen finden. Der intuitivste, aber auch der schwierigste ist der rekursive Algorithmus, bei dem wir das erste Zeichen aus der Sequenz auswählen und dann das zweite, dritte usw. rekursiv auswählen, bis alle Zeichen aus der Sequenz ausgewählt sind. Es ist klar, dass die Komplexität eines solchen Algorithmus O (n!) Ist.

Es stellt sich jedoch heraus, dass der einfachste Algorithmus zum Erzeugen aller Permutationen in lexikografischer Reihenfolge darin besteht, mit der kleinsten zu beginnen und die nächste vorhandene Permutation wiederholt zu berechnen. Mal sehen, wie es geht.

Genau wie bei der Berechnung des nächsten ganzzahligen Werts sollten wir versuchen, die rechte Seite der Sequenz zu vergrößern und die linke Seite unverändert zu lassen.

Nehmen Sie als Beispiel die obige Sequenz - (0, 1, 2, 5, 3, 3, 0). Um die Sequenz höher als die ursprüngliche zu erhalten, reicht es aus, das erste und das zweite Element neu anzuordnen. Dies ist jedoch nicht erforderlich, da Sie das zweite und dritte Element neu anordnen und eine Sequenz erhalten können, die in aufsteigender Reihenfolge näher liegt. was uns zur nächsten näheren Permutation usw. führen wird.

Der optimalste Algorithmus wäre in diesem Fall der folgende:

1. Zunächst müssen Sie das größte nicht zunehmende Suffix finden. Im obigen Beispiel wäre dies - (5, 3, 3, 0). Wenn Sie versuchen, eine Permutation in dieser Reihenfolge vorzunehmen, ist diese nicht höher als die ursprüngliche.
   Es ist erwähnenswert, dass Sie diese Sequenz in O (n) -Zeit finden können, indem Sie die Sequenz von links nach rechts betrachten.
2. Das nächste Element aus dem Suffix ist der Drehpunkt. In unserem Fall ist dies 2. Der Drehpunkt ist immer kleiner als das erste Element des Suffix. Dies bedeutet, dass es im Suffix sicherlich ein Element gibt, das den Drehpunkt überschreitet, und wenn wir den Drehpunkt vom Suffix, das das Drehpunkt-Stützelement überschreitet, zum kleinsten Element ändern, erhalten wir eine Sequenz, die das ursprüngliche überschreitet - in unserem Fall ist es (0, 1, 3, 5) , 3, 2, 0).
   Das heißt, Das Ergebnis dieser Operation ist das minimal mögliche aufsteigende Präfix.
   
3. Und im letzten Schritt müssen wir das Suffix in aufsteigender Reihenfolge sortieren. Das heißt, Wir erhalten das kleinstmögliche Suffix. In unserem Beispiel ist dies (0, 2, 3, 5) und die gesamte Sequenz sieht aus wie (0, 1, 3, 0, 2, 3, 5).
   

Dieser Wert ist die nächste lexikografische Neuanordnung.



Die praktische Anwendung des Algorithmus habe ich während meiner gesamten Arbeit nie gebraucht, aber für ein Interview mit Uber dachten sie anders :))

Der Einfachheit halber wird der gesamte Code in Go geschrieben, und ich denke, es ist für jeden einfach, ihn in eine andere Programmiersprache zu übersetzen.

Vielen Dank an PYXRU und 646f67, die mich mit einer Nase in eine mögliche Optimierung des Algorithmus hineingesteckt haben - um die Permutation für lineare Komplexität einfach mit dem umgekehrten Suffix zu berechnen.

func NextPermutationAlgorithm(w string) string { l := len(w) b := []byte(w) r := "no answer" for i:=l-1; i>0 ; i--{ if b[i-1] < b[i] { pivot := i for j := pivot; j < l; j++ { if b[j] <= b[pivot] && b[i-1] < b[j] { pivot = j } } b[i-1], b[pivot] = b[pivot], b[i-1] for j := l-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } r = string(b) break } } return r }