Wie können wir die N-te Permutation einer Menge direkt finden, ohne alle vorherigen Permutationen zu generieren?

Die n-te Permutation direkt ermitteln

Die Aufgabe besteht darin, die n-te Permutation einer Menge von Elementen zu finden, ohne alle explizit zu berechnen die vorherigen Permutationen. Dies kann mit einem cleveren Algorithmus namens Faktoradischer Algorithmus erreicht werden.

Der Faktoradische Algorithmus nutzt die faktorielle Zerlegung des Permutationsindex. Indem wir wiederholt eine euklidische Division mit Fakultätszahlen durchführen, erhalten wir eine Reihe von Quotienten, die die Permutation darstellen.

So funktioniert der Algorithmus:

1. Fakultäre Zerlegung: Teilen Sie den Permutationsindex n durch die Fakultät von (n-1)!, (n-2)! usw. Die Quotienten werden in einem Array gespeichert.
2. Permutationsdarstellung:Jeder Quotient stellt den Index des aus den übrigen Elementen ausgewählten Elements dar.
3. Anpassung: Da die Quotienten vorhergehende Werte nicht berücksichtigen, müssen sie angepasst werden, um die korrekte Permutation widerzuspiegeln. Erhöhen Sie jeden Quotienten um die Anzahl der vorhergehenden Quotienten, die kleiner oder gleich ihm sind.

Lassen Sie uns zum Beispiel die 3. Permutation von {'A', 'B', 'C'} finden.

• n = 3
• Quotienten: [1, 0, 0]
• Angepasste Quotienten: [1, 0, 1]

Die Permutation ist somit „B“, „A“, „C“, was tatsächlich die 3. Permutation von ist die gegebene Menge.

Der bereitgestellte C-Code implementiert den Faktoradischen Algorithmus und zeigt, wie man die n-te Permutation direkt erhält ohne die vorherigen zu berechnen.

Das obige ist der detaillierte Inhalt vonWie können wir die N-te Permutation einer Menge direkt finden, ohne alle vorherigen Permutationen zu generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!