Leniwe generowanie permutacji

Szukam algorytmu do generowania permutacji zestawu w taki sposób, żebym mógł zrobić leniwą ich listę w Clojure. tj. chciałbym powtórzyć listę permutacji, w przypadku której każda permutacja nie jest obliczana, dopóki o nią nie poproszę, a wszystkie permutacje nie muszą być przechowywane w pamięci naraz.

Alternatywnie szukam algorytmu, w którym dany zestaw zwróci „następną” permutację tego zestawu, w taki sposób, że wielokrotne wywoływanie funkcji na własnym wyjściu będzie cyklicznie przechodziło przez wszystkie permutacje oryginalnego zestawu, w jakiś porządek (kolejność nie ma znaczenia).

Czy istnieje taki algorytm? Większość algorytmów generujących permutacje, które widziałem, generuje je wszystkie naraz (zwykle rekurencyjnie), co nie jest skalowane do bardzo dużych zbiorów. Implementacja w Clojure (lub innym języku funkcjonalnym) byłaby pomocna, ale mogę to rozgryźć z pseudokodu.

Tak, tam jest algorytm „obok permutacja”, i to całkiem proste zbyt. Biblioteka standardowych szablonów C ++ (STL) ma nawet funkcję o nazwie next_permutation.

Algorytm faktycznie znajduje następną permutację - leksykograficznie następną. Idea jest taka: załóżmy, że otrzymujesz sekwencję, powiedz „32541”. Jaka jest następna permutacja?

Jeśli się nad tym zastanowisz, zobaczysz, że to „34125”. Twoje myśli były prawdopodobnie takie: w „32541”

• nie ma sposobu, aby zachować stałą „32” i znaleźć późniejszą permutację w części „541”, ponieważ ta permutacja jest już ostatnią dla 5,4 i 1 - jest posortowana malejąco.
• Będziesz więc musiał zmienić „2” na coś większego - w rzeczywistości na najmniejszą liczbę większą niż w części „541”, czyli 4.
• Teraz, gdy już zdecydujesz, że permutacja rozpocznie się od „34”, pozostałe liczby powinny być w kolejności rosnącej, więc odpowiedź brzmi „34125”.

Algorytm ma zaimplementować dokładnie ten tok rozumowania:

1. Znajdź najdłuższy „ogon” w kolejności malejącej. (Część „541”).
2. Zmień liczbę tuż przed końcem („2”) na najmniejszą, większą niż w końcu (4).
3. Posortuj ogon w kolejności rosnącej.

Możesz to zrobić (1.) efektywnie, zaczynając od końca i cofając się, o ile poprzedni element nie jest mniejszy niż obecny. Możesz to zrobić (2.), po prostu zamieniając „4” na „2”, aby uzyskać „34521”. Gdy to zrobisz, możesz uniknąć korzystania z algorytmu sortowania dla (3.), ponieważ koniec był i jest nadal (pomyśl o tym) posortowany w kolejności malejącej, więc wystarczy go tylko odwrócić.

Kod C ++ robi dokładnie to (spójrz na źródło w /usr/include/c++/4.0.0/bits/stl_algo.htwoim systemie lub zobacz ten artykuł ); przetłumaczenie go na swój język powinno być proste: [Przeczytaj „BidirectionalIterator” jako „wskaźnik”, jeśli nie znasz iteratorów C ++. Kod powraca, falsejeśli nie ma następnej permutacji, tj. Jesteśmy już w kolejności malejącej.]

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;
        }
    }
}

Mogłoby się wydawać, że może to zająć O (n) czasu na każdą permutację, ale jeśli się nad tym zastanowić, możesz udowodnić, że zajmuje to O (n!) Czasu łącznie dla wszystkich permutacji, więc tylko O ​​(1) - stały czas - na permutację.

Dobrą rzeczą jest to, że algorytm działa nawet wtedy, gdy masz sekwencję z powtarzającymi się elementami: powiedzmy „232254421” znajdzie ogon jako „54421”, zamień „2” i „4” (więc „232454221” ), odwróć resztę, dając „232412245”, czyli następną permutację.

Zakładając, że mówimy o porządku leksykograficznym nad permutowanymi wartościami, istnieją dwa ogólne podejścia, których można użyć:

1. przekształcić jedną permutację elementów do następnej permutacji (jak opublikował ShreevatsaR) lub
2. bezpośrednio obliczyć nth permutację, licząc nod 0 w górę.

Dla tych (takich jak ja ;-), którzy nie znają języka C ++ jako rodzimego, podejście 1 można zaimplementować z następującego pseudokodu, zakładając indeksowanie tablicy z indeksem zero po lewej stronie (podstawiając inną strukturę , takie jak lista, jest „pozostawione jako ćwiczenie” ;-):

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

Oto przykład zaczynający się od aktualnej permutacji CADB:

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

W przypadku drugiego podejścia (bezpośrednie obliczenie ntej permutacji) pamiętaj, że istnieją N!permutacje Nelementów. Dlatego też, jeśli permutujesz Nelementy, pierwsze (N-1)!permutacje muszą zaczynać się od najmniejszego elementu, następne (N-1)!permutacje muszą zaczynać się od drugiego najmniejszego i tak dalej. Prowadzi to do następującego podejścia rekurencyjnego (ponownie w pseudokodzie, numerując permutacje i pozycje od 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

Na przykład 13. permutacja ABCD znajduje się w następujący sposób:

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

Nawiasem mówiąc, „usuwanie” elementów może być reprezentowane przez równoległą tablicę wartości logicznych, która wskazuje, które elementy są nadal dostępne, więc nie jest konieczne tworzenie nowej tablicy przy każdym wywołaniu rekurencyjnym.

Tak więc, aby iterować po permutacjach ABCD, po prostu policz od 0 do 23 (4! -1) i bezpośrednio oblicz odpowiednią permutację.

Powinieneś sprawdzić artykuł Permutations na Wikipedii. Istnieje również koncepcja liczb czynnikowych .

Zresztą problem matematyczny jest dość trudny.

W C#możesz użyć iteratori zatrzymać algorytm permutacji za pomocą yield. Problem polega na tym, że nie możesz chodzić tam i z powrotem ani używać pliku index.

Więcej przykładów algorytmów permutacji do ich generowania.

Źródło: http://www.ddj.com/architect/201200326

1. Wykorzystuje algorytm Fike'a, czyli jeden z najszybciej znanych.
2. Używa algorytmu do kolejności leksograficznej.
3. Używa metody nieleksograficznej, ale działa szybciej niż pozycja 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.

funkcja permutacji w clojure.contrib.lazy_seqs już twierdzi, że właśnie to robi.