Es gibt verschiedene oder schlechtere Lösungen, aber ich suche nach einer, die läuft oder ein Beweis, dass es keine gibt.
Es gibt verschiedene oder schlechtere Lösungen, aber ich suche nach einer, die läuft oder ein Beweis, dass es keine gibt.
Die Arbeit Linear-Time Ranking of Permutations aus dem Jahr 2007 liefert einen linearen Time Ranking-Algorithmus für die lexikografische Reihenfolge unter der Annahme einer Arithmetik für Längenzahlen braucht konstante Zeit.
Die 2001 erschienene Arbeit Ranking and Unranking Permutations in linearer Zeit präsentiert einen linearen Time Ranking-Algorithmus, der keine schnelle Arithmetik für große Zahlen erfordert, jedoch nicht für die lexikografische Reihenfolge. Zu letzterem heißt es
Das gesamte Problem der Rangfolge von Permutationen in lexikografischer Reihenfolge scheint untrennbar mit dem Problem der Berechnung der Anzahl von Inversionen in einer Permutation verbunden zu sein, und es scheint, dass ein großer Durchbruch erforderlich sein wird, um diese Berechnung in linearer Zeit durchzuführen, wenn dies überhaupt möglich ist .
Auf der anderen Seite erwähnt es eine Algorithmus zur Einstufung von Permutationen in lexikographischer Reihenfolge aufgrund von Dietz.
Da die Antwort bereits gut ist, werde ich hier eine weitere (neuere) Referenz hinzufügen:
schlägt eine Methode vor, um Permutationen in lexikografischer Reihenfolge zu generieren, zu ordnen und zu entfernen, sowie einige neue Funktionen wie das Generieren einer Permutation, die einen bestimmten Abstand von einer anderen Permutation entfernt ist.
Komplexität ist wieder von der Auftrag