Faul Permutationen erzeugen

86

Ich suche nach einem Algorithmus, um Permutationen einer Menge so zu generieren, dass ich sie in Clojure faul auflisten kann. Das heißt, ich möchte eine Liste von Permutationen durchlaufen, bei denen jede Permutation erst berechnet wird, wenn ich sie anfordere, und nicht alle Permutationen gleichzeitig im Speicher gespeichert werden müssen.

Alternativ suche ich nach einem Algorithmus, bei dem bei einer bestimmten Menge die "nächste" Permutation dieser Menge zurückgegeben wird, so dass durch wiederholtes Aufrufen der Funktion an ihrer eigenen Ausgabe alle Permutationen der ursprünglichen Menge in durchlaufen werden eine Reihenfolge (was die Reihenfolge ist, spielt keine Rolle).

Gibt es einen solchen Algorithmus? Die meisten der permutationsgenerierenden Algorithmen, die ich gesehen habe, generieren sie alle auf einmal (normalerweise rekursiv), was sich nicht auf sehr große Mengen skalieren lässt. Eine Implementierung in Clojure (oder einer anderen funktionalen Sprache) wäre hilfreich, aber ich kann es anhand des Pseudocodes herausfinden.

Brian Carper
quelle

Antworten:

138

Ja, es gibt einen "Next Permutation" -Algorithmus, der auch recht einfach ist. Die C ++ Standard Template Library (STL) hat sogar eine Funktion namensnext_permutation .

Der Algorithmus findet tatsächlich die nächste Permutation - die lexikographisch nächste. Die Idee ist folgende: Angenommen, Sie erhalten eine Sequenz, sagen Sie "32541". Was ist die nächste Permutation?

Wenn Sie darüber nachdenken, werden Sie sehen, dass es "34125" ist. Und Ihre Gedanken waren wahrscheinlich so: In "32541",

  • Es gibt keine Möglichkeit, die "32" festzuhalten und eine spätere Permutation im "541" -Teil zu finden, da diese Permutation bereits die letzte für 5,4 und 1 ist - sie wird in absteigender Reihenfolge sortiert.
  • Sie müssen also die "2" in etwas Größeres ändern - tatsächlich in die kleinste Zahl, die größer ist als im "541" -Teil, nämlich 4.
  • Sobald Sie entschieden haben, dass die Permutation mit "34" beginnt, sollten die restlichen Zahlen in aufsteigender Reihenfolge angezeigt werden, sodass die Antwort "34125" lautet.

Der Algorithmus soll genau diese Argumentation implementieren:

  1. Finden Sie den längsten "Schwanz", der in absteigender Reihenfolge bestellt wird. (Der Teil "541".)
  2. Ändern Sie die Zahl kurz vor dem Schwanz (die "2") in die kleinste Zahl, die größer ist als die im Schwanz (die 4).
  3. Sortieren Sie den Schwanz in aufsteigender Reihenfolge.

Sie können (1.) effizient ausführen, indem Sie am Ende beginnen und rückwärts gehen, solange das vorherige Element nicht kleiner als das aktuelle Element ist. Sie können (2.) tun, indem Sie einfach die "4" mit der "2" tauschen, so dass Sie "34521" haben. Sobald Sie dies tun, können Sie die Verwendung eines Sortieralgorithmus für (3.) vermeiden, da der Schwanz war und ist (denken Sie darüber nach) in absteigender Reihenfolge sortiert, so dass es nur umgekehrt werden muss.

Der C ++ - Code macht genau das (sehen Sie sich die Quelle /usr/include/c++/4.0.0/bits/stl_algo.hauf Ihrem System an oder lesen Sie diesen Artikel ). Es sollte einfach sein, es in Ihre Sprache zu übersetzen: [Lesen Sie "BidirectionalIterator" als "Zeiger", wenn Sie mit C ++ - Iteratoren nicht vertraut sind. Der Code wird zurückgegeben, falsewenn keine nächste Permutation vorliegt , dh wir befinden uns bereits in absteigender Reihenfolge.]

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

Es mag scheinen, dass es O (n) Zeit pro Permutation dauern kann, aber wenn Sie genauer darüber nachdenken, können Sie beweisen, dass es O (n!) Zeit für alle Permutationen insgesamt braucht, also nur O (1) - konstante Zeit - pro Permutation.

Das Gute ist, dass der Algorithmus auch dann funktioniert, wenn Sie eine Sequenz mit wiederholten Elementen haben: Mit beispielsweise "232254421" würde er den Schwanz als "54421" finden, die "2" und "4" tauschen (also "232454221"). ), kehren Sie den Rest um und geben Sie "232412245" an, was die nächste Permutation ist.

ShreevatsaR
quelle
2
Dies funktioniert, vorausgesetzt, Sie haben eine Gesamtreihenfolge für die Elemente.
Chris Conway
10
Wenn Sie mit einer Menge beginnen, können Sie eine Gesamtreihenfolge für die Elemente beliebig definieren. Ordnen Sie die Elemente unterschiedlichen Zahlen zu. :-)
ShreevatsaR
3
Diese Antwort bekommt einfach nicht genug Upvotes, aber ich kann sie nur einmal upvoten ... :-)
Daniel C. Sobral
1
@ Masse: Nicht genau ... ungefähr, Sie können von 1 zu einer größeren Zahl gehen. Beispiel: Beginnen Sie mit 32541. Der Schwanz ist 541. Nach den erforderlichen Schritten ist die nächste Permutation 34125. Jetzt ist der Schwanz nur noch 5. Inkrementieren Sie 3412 mit der 5 und tauschen Sie, die nächste Permutation ist 34152. Jetzt ist der Schwanz 52, von Länge 2. Dann wird es 34215 (Schwanzlänge 1), 34251 (Schwanzlänge 2), 34512 (Länge 1), 34521 (Länge 3), 35124 (Länge 1) usw. Sie haben Recht, dass der Schwanz ist Die meiste Zeit klein, weshalb der Algorithmus über mehrere Anrufe hinweg eine gute Leistung aufweist.
ShreevatsaR
1
@ SamStoelinga: Du hast eigentlich recht. O (n log n) ist O (log n!). Ich hätte O (n!) Sagen sollen.
ShreevatsaR
42

Angenommen, es handelt sich um eine lexikografische Reihenfolge über die permutierten Werte, gibt es zwei allgemeine Ansätze, die Sie verwenden können:

  1. transformiere eine Permutation der Elemente in die nächste Permutation (wie von ShreevatsaR gepostet) oder
  2. Berechnen Sie direkt die nth-Permutation, während Sie nvon 0 aufwärts zählen.

Für diejenigen (wie ich ;-), die kein C ++ als Muttersprachler sprechen, kann Ansatz 1 aus dem folgenden Pseudocode implementiert werden, wobei eine auf Null basierende Indizierung eines Arrays mit dem Index Null auf der "linken Seite" angenommen wird (wobei eine andere Struktur ersetzt wird) , wie eine Liste, wird "als Übung belassen" ;-):

1. scan the array from right-to-left (indices descending from N-1 to 0)
1.1. if the current element is less than its right-hand neighbor,
     call the current element the pivot,
     and stop scanning
1.2. if the left end is reached without finding a pivot,
     reverse the array and return
     (the permutation was the lexicographically last, so its time to start over)
2. scan the array from right-to-left again,
   to find the rightmost element larger than the pivot
   (call that one the successor)
3. swap the pivot and the successor
4. reverse the portion of the array to the right of where the pivot was found
5. return

Hier ist ein Beispiel, das mit einer aktuellen Permutation von CADB beginnt:

1. scanning from the right finds A as the pivot in position 1
2. scanning again finds B as the successor in position 3
3. swapping pivot and successor gives CBDA
4. reversing everything following position 1 (i.e. positions 2..3) gives CBAD
5. CBAD is the next permutation after CADB

Denken Sie beim zweiten Ansatz (direkte Berechnung der dritten nPermutation) daran, dass es N!Permutationen von NElementen gibt. Wenn Sie also NElemente permutieren , müssen die ersten (N-1)!Permutationen mit dem kleinsten Element beginnen, die nächsten (N-1)!Permutationen müssen mit dem zweitkleinsten beginnen und so weiter. Dies führt zu folgendem rekursiven Ansatz (wiederum im Pseudocode, Nummerierung der Permutationen und Positionen von 0):

To find permutation x of array A, where A has N elements:
0. if A has one element, return it
1. set p to ( x / (N-1)! ) mod N
2. the desired permutation will be A[p] followed by
   permutation ( x mod (N-1)! )
   of the elements remaining in A after position p is removed

So wird zum Beispiel die 13. Permutation von ABCD wie folgt gefunden:

perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}
C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}
  perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}
  A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}
    perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}
    D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}
      B (because there's only one element)
    DB
  ADB
CADB

Im Übrigen kann das "Entfernen" von Elementen durch ein paralleles Array von Booleschen Werten dargestellt werden, das angibt, welche Elemente noch verfügbar sind, sodass nicht bei jedem rekursiven Aufruf ein neues Array erstellt werden muss.

Um die Permutationen von ABCD zu durchlaufen, zählen Sie einfach von 0 bis 23 (4! -1) und berechnen Sie die entsprechende Permutation direkt.

joel.neely
quelle
1
++ Ihre Antwort wird unterschätzt. Nicht von der akzeptierten Antwort wegzunehmen, aber der zweite Ansatz ist mächtiger, weil er auch auf Kombinationen verallgemeinert werden kann. Eine vollständige Diskussion würde die umgekehrte Funktion von Sequenz zu Index zeigen.
Stirb in Sente
Tatsächlich. Ich stimme dem vorherigen Kommentar zu - obwohl meine Antwort etwas weniger Operationen für die spezifische gestellte Frage ausführt, ist dieser Ansatz allgemeiner, da er beispielsweise dazu dient, die Permutation zu finden, die K Schritte von einer bestimmten entfernt ist.
ShreevatsaR
3

Sie sollten den Permutations-Artikel über Wikipeda lesen. Es gibt auch das Konzept der faktoradischen Zahlen.

Wie auch immer, das mathematische Problem ist ziemlich schwer.

In können C#Sie ein verwenden iteratorund den Permutationsalgorithmus mit stoppen yield. Das Problem dabei ist, dass Sie nicht hin und her gehen oder eine verwenden können index.

Bogdan Maxim
quelle
4
"Wie auch immer, das mathematische Problem ist ziemlich schwer." Nein, ist es nicht :-)
ShreevatsaR
Nun, es ist ... wenn Sie nicht über faktoradische Zahlen Bescheid wissen, gibt es keine Möglichkeit, in einer akzeptablen Zeit einen geeigneten Algorithmus zu finden. Es ist, als würde man versuchen, eine Gleichung 4. Grades zu lösen, ohne die Methode zu kennen.
Bogdan Maxim
1
Oh, tut mir leid, ich dachte, Sie sprechen über das ursprüngliche Problem. Ich verstehe immer noch nicht, warum Sie sowieso "faktoradische Zahlen" brauchen ... es ist ziemlich einfach, jedem der n eine Zahl zuzuweisen! Permutationen einer gegebenen Menge und Konstruieren einer Permutation aus einer Zahl. [Nur ein
bisschen
1
Im idiomatischen C # wird ein Iterator korrekter als Enumerator bezeichnet .
Drew Noakes
@ShreevatsaR: Wie würden Sie das tun, ohne alle Permutationen zu generieren? Zum Beispiel, wenn Sie die n-te Permutation generieren mussten.
Jacob
3

Weitere Beispiele für Permutationsalgorithmen, um sie zu generieren.

Quelle: http://www.ddj.com/architect/201200326

  1. Verwendet den Fike-Algorithmus, der am schnellsten bekannt ist.
  2. Verwendet den Algo zur lexografischen Reihenfolge.
  3. Verwendet das Nicht-Flexografische, läuft jedoch schneller als Element 2.

1.


PROGRAM TestFikePerm;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write ;
WriteLn;
permcount := permcount + 1;
END;

PROCEDURE FikePerm ;
{Outputs permutations in nonlexicographic order.  This is Fike.s algorithm}
{ with tuning by J.S. Rohl.  The array marks[1..marksizn] is global.  The   }
{ procedure WriteArray is global and displays the results.  This must be}
{ evoked with FikePerm(2) in the calling procedure.}
VAR
    dn, dk, temp : INTEGER;
BEGIN
IF 
THEN BEGIN { swap the pair }
    WriteArray;
    temp :=marks[marksize];
    FOR dn :=  DOWNTO 1
    DO BEGIN
        marks[marksize] := marks[dn];
        marks [dn] := temp;
        WriteArray;
        marks[dn] := marks[marksize]
        END;
    marks[marksize] := temp;
    END {of bottom level sequence }
ELSE BEGIN
    FikePerm;
    temp := marks[k];
    FOR dk :=  DOWNTO 1
    DO BEGIN
        marks[k] := marks[dk];
        marks[dk][ := temp;
        FikePerm;
        marks[dk] := marks[k];
        END; { of loop on dk }
    marks[k] := temp;l
    END { of sequence for other levels }
END; { of FikePerm procedure }

BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii;
permcount := 0;
WriteLn ;
WrieLn;
FikePerm ; { It always starts with 2 }
WriteLn ;
ReadLn;
END.

2.


PROGRAM TestLexPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray; VAR i : INTEGER; BEGIN FOR i := 1 TO marksize DO Write ; permcount := permcount + 1; WriteLn; END;

PROCEDURE LexPerm ; { Outputs permutations in lexicographic order. The array marks is global } { and has n or fewer marks. The procedure WriteArray () is global and } { displays the results. } VAR work : INTEGER: mp, hlen, i : INTEGER; BEGIN IF THEN BEGIN { Swap the pair } work := marks[1]; marks[1] := marks[2]; marks[2] := work; WriteArray ; END ELSE BEGIN FOR mp := DOWNTO 1 DO BEGIN LexPerm<>; hlen := DIV 2; FOR i := 1 TO hlen DO BEGIN { Another swap } work := marks[i]; marks[i] := marks[n - i]; marks[n - i] := work END; work := marks[n]; { More swapping } marks[n[ := marks[mp]; marks[mp] := work; WriteArray; END; LexPerm<> END; END;

BEGIN { Main } FOR ii := 1 TO marksize DO marks[ii] := ii; permcount := 1; { The starting position is permutation } WriteLn < Starting position: >; WriteLn LexPerm ; WriteLn < PermCount is , permcount>; ReadLn; END.

3.


PROGRAM TestAllPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] of INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray; VAR i : INTEGER; BEGIN FOR i := 1 TO marksize DO Write ; WriteLn; permcount := permcount + 1; END;

PROCEDURE AllPerm (n : INTEGER); { Outputs permutations in nonlexicographic order. The array marks is } { global and has n or few marks. The procedure WriteArray is global and } { displays the results. } VAR work : INTEGER; mp, swaptemp : INTEGER; BEGIN IF THEN BEGIN { Swap the pair } work := marks[1]; marks[1] := marks[2]; marks[2] := work; WriteArray; END ELSE BEGIN FOR mp := DOWNTO 1 DO BEGIN ALLPerm<< n - 1>>; IF > THEN swaptemp := 1 ELSE swaptemp := mp; work := marks[n]; marks[n] := marks[swaptemp}; marks[swaptemp} := work; WriteArray; AllPerm< n-1 >; END; END;

BEGIN { Main } FOR ii := 1 TO marksize DO marks[ii] := ii permcount :=1; WriteLn < Starting position; >; WriteLn; Allperm < marksize>; WriteLn < Perm count is , permcount>; ReadLn; END.

Carlos Eduardo Olivieri
quelle
2

Die Permutationsfunktion in clojure.contrib.lazy_seqs behauptet bereits, genau dies zu tun.


quelle
Danke, ich war mir dessen nicht bewusst. Es behauptet, faul zu sein, aber leider funktioniert es sehr schlecht und läuft leicht über den Stapel.
Brian Carper
Faulheit kann sicherlich zu Stapelüberläufen führen, wie zum Beispiel in dieser Antwort erläutert .
Crockeea