Wie kann ich die n-te Permutation berechnen (oder die lexikografische Reihenfolge einer bestimmten Permutation angeben)?

Jakub Arnold

Diese Frage besteht aus zwei Teilen. Da ich jedoch versuche, mit einer Prolog-Implementierung fertig zu werden, führt die Lösung eines Problems wahrscheinlich sofort zu einer Lösung des anderen.

  1. {1,2,...,N}Wie kann ich bei einer Permutation einer Liste von Ganzzahlen feststellen, wie hoch der Index dieser Permutation in lexikografischer Reihenfolge ist?
  2. kWie kann ich bei gegebener Zahl die k-te Permutation von Zahlen berechnen {1,2...,N}?

Ich suche nach einem Algorithmus, der dies einigermaßen besser kann, als nur eine next permutationFunktionszeit zu iterieren k. Afaik sollte es möglich sein, beide direkt zu berechnen.

Was ich mir bisher ausgedacht habe, ist, dass ich anhand der Zahlen von links erkennen kann, wie viele Permutationen vor jeder Zahl in einem bestimmten Index waren, und diese dann irgendwie kombinieren kann, aber ich bin mir nicht sicher, ob dies zu einem führt richtige Lösung.

IVlad

Ich werde nur den Entwurf einer Lösung für jede geben:

Wie kann ich bei einer Permutation einer Liste von ganzen Zahlen {1,2, ..., N} feststellen, wie hoch der Index dieser Permutation in lexikografischer Reihenfolge ist?

Fragen Sie sich dazu, mit wie vielen Permutationen beginnen 1? Es gibt (N - 1)!. Lassen Sie uns nun ein Beispiel machen:

3 1 2

Wie viele Permutationen 1 2 3beginnen mit 1oder 2? 2*2!. Dieser muss hinter diesen her sein, also ist sein Index mindestens 2*2! = 4. Überprüfen Sie nun das nächste Element. Mit wie vielen Permutationen 1 2beginnen Sie 0? Keiner. Sie sind fertig, der Index ist 4. Sie können hinzufügen, 1wenn Sie eine 1-basierte Indizierung verwenden möchten .

Wie kann ich bei einer gegebenen Zahl k die k-te Permutation von Zahlen {1,2 ..., N} berechnen?

Gegeben 4, wie wir bekommen können 3 1 2? Wir müssen jedes Element finden.

Was können wir auf der ersten Position haben? Wenn 1ja, kann der maximale Index sein 2! - 1 = 1(ich verwende eine nullbasierte Indizierung). Wenn wir haben 2, kann das Maximum sein 2*2! - 1 = 3. Wenn wir haben 3, kann das Maximum sein 5. Also müssen wir haben 3:

3

Nun haben wir das Problem zu finden , die reduzierten 4 - 2*2! = 0-te Permutation 1 2, das ist 1 2(man kann über sie Grund rekursiv wie oben).

Verwandte Artikel

Wie bekomme ich die Permutation einer Tabelle?

ANZEIGE : Ich habe eine Tabelle mit 10 Spalten. Ich möchte alle möglichen Permutationen erhalten. Beispiel für eine Tabelle mit 3 Spalten: col1 col2 col3 10 40 3, 20 6 1, Die Permutationstabelle lautet: col1 col2 col3 10

Wie finde ich die inverse Permutation?

Was Angenommen, ich habe einen unbekannten Vektor vund eine Permutation p. Wie kann ich vaus v(p)und rekonstruieren p? Eine äquivalente Frage wäre, eine qsolche Permutation zu finden, dass p(q) = [1 2 ... n]? Da dies in einer engen Schleife ablaufen wird, muss

Wie kann ich die Stadt in einer Kleinanzeigenliste angeben?

ivan73 Ich habe eine Liste von Kleinanzeigen, für die ich das ProductSchema verwende. Ich möchte auch die in der Anzeige angegebene Stadt markieren (mit Mikrodaten). Wie kann ich das machen? Shannon Young In der Dokumentation sieht es so aus, als wäre Angebot