Menghasilkan permutasi dengan malas

Saya mencari algoritme untuk menghasilkan permutasi satu set sedemikian rupa sehingga saya bisa membuat daftar malas dari mereka di Clojure. yaitu Saya ingin mengulang daftar permutasi di mana setiap permutasi tidak dihitung sampai saya memintanya, dan semua permutasi tidak harus disimpan dalam memori sekaligus.

Alternatifnya, saya sedang mencari algoritme di mana diberikan himpunan tertentu, ia akan mengembalikan permutasi "berikutnya" dari himpunan itu, sedemikian rupa sehingga berulang kali memanggil fungsi pada keluarannya sendiri akan menggilir semua permutasi dari himpunan asli, di beberapa urutan (apa urutannya tidak masalah).

Apakah ada algoritma seperti itu? Sebagian besar algoritme penghasil permutasi yang pernah saya lihat cenderung menghasilkan semuanya sekaligus (biasanya secara rekursif), yang tidak berskala ke set yang sangat besar. Implementasi di Clojure (atau bahasa fungsional lainnya) akan membantu tetapi saya dapat mengetahuinya dari pseudocode.

Ya, ada adalah sebuah "permutasi berikutnya" algoritma, dan itu cukup sederhana juga. Pustaka template standar (STL) C ++ bahkan memiliki fungsi yang dipanggil next_permutation.

Algoritme sebenarnya menemukan permutasi berikutnya - permutasi berikutnya secara leksikografis. Idenya adalah ini: misalkan Anda diberi urutan, katakan "32541". Apa permutasi selanjutnya?

Jika Anda memikirkannya, Anda akan melihat bahwa itu adalah "34125". Dan pikiran Anda mungkin adalah seperti ini: Dalam "32541",

• tidak ada cara untuk menjaga "32" tetap dan menemukan permutasi yang lebih baru di bagian "541", karena permutasi itu sudah yang terakhir untuk 5,4, dan 1 - itu diurutkan dalam urutan menurun.
• Jadi Anda harus mengubah "2" menjadi sesuatu yang lebih besar - pada kenyataannya, ke angka terkecil yang lebih besar daripada di bagian "541", yaitu 4.
• Sekarang, setelah Anda memutuskan bahwa permutasi akan dimulai dengan "34", sisa angka harus dalam urutan yang meningkat, jadi jawabannya adalah "34125".

Algoritme akan mengimplementasikan secara tepat garis penalaran itu:

1. Temukan "ekor" terpanjang yang diurutkan dalam urutan menurun. (Bagian "541".)
2. Ubah angka sebelum ekor ("2") ke angka terkecil yang lebih besar dari pada ekor (4).
3. Urutkan ekor dalam urutan meningkat.

Anda dapat melakukan (1.) secara efisien dengan memulai dari akhir dan mundur selama elemen sebelumnya tidak lebih kecil dari elemen saat ini. Anda dapat melakukan (2.) dengan hanya menukar "4" dengan '2 ", sehingga Anda akan memiliki" 34521 ". Setelah Anda melakukan ini, Anda dapat menghindari penggunaan algoritma pengurutan untuk (3.), karena tail tadinya, dan masih (pikirkan tentang ini), diurutkan dalam urutan menurun, jadi hanya perlu dibalik.

Kode C ++ melakukan hal ini dengan tepat (lihat sumber di /usr/include/c++/4.0.0/bits/stl_algo.hsistem Anda, atau lihat artikel ini ); seharusnya mudah untuk menerjemahkannya ke bahasa Anda: [Baca "BidirectionalIterator" sebagai "pointer", jika Anda tidak terbiasa dengan iterator C ++. Kode kembali falsejika tidak ada permutasi berikutnya, yaitu kita sudah dalam urutan menurun.]

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

Tampaknya dibutuhkan O (n) waktu per permutasi, tetapi jika Anda memikirkannya lebih hati-hati, Anda dapat membuktikan bahwa dibutuhkan O (n!) Waktu untuk semua permutasi secara total, jadi hanya O (1) - waktu konstan - per permutasi.

Hal baiknya adalah bahwa algoritme bekerja bahkan ketika Anda memiliki urutan dengan elemen yang berulang: dengan, katakanlah, "232254421", algoritme akan menemukan ekor sebagai "54421", menukar "2" dan "4" (jadi "232454221" ), membalikkan sisanya, memberikan "232412245", yang merupakan permutasi berikutnya.

Dengan asumsi bahwa kita berbicara tentang urutan leksikografik di atas nilai yang diubah, ada dua pendekatan umum yang dapat Anda gunakan:

1. mengubah satu permutasi elemen ke permutasi berikutnya (seperti yang diposting ShreevatsaR), atau
2. langsung menghitung npermutasi th, sambil menghitung ndari 0 ke atas.

Bagi mereka (seperti saya ;-) yang tidak berbicara c ++ sebagai native, pendekatan 1 dapat diimplementasikan dari pseudo-code berikut, dengan asumsi pengindeksan berbasis-nol dari sebuah array dengan indeks nol di "kiri" (menggantikan beberapa struktur lain , seperti daftar, "ditinggalkan sebagai latihan" ;-):

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

Berikut adalah contoh yang dimulai dengan permutasi CADB saat ini:

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

Untuk pendekatan kedua (perhitungan langsung npermutasi th), ingatlah bahwa ada N!permutasi Nelemen. Oleh karena itu, jika Anda mengubah Nelemen, (N-1)!permutasi pertama harus dimulai dengan elemen terkecil, (N-1)!permutasi berikutnya harus dimulai dengan yang terkecil kedua, dan seterusnya. Ini mengarah ke pendekatan rekursif berikut (sekali lagi dalam pseudo-code, penomoran permutasi dan posisi dari 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

Jadi, misalnya, permutasi ke-13 ABCD ditemukan sebagai berikut:

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

Kebetulan, "penghapusan" elemen dapat diwakili oleh array paralel dari boolean yang menunjukkan elemen mana yang masih tersedia, sehingga tidak perlu membuat array baru pada setiap panggilan rekursif.

Jadi, untuk mengulangi permutasi ABCD, hitung saja dari 0 hingga 23 (4! -1) dan langsung hitung permutasi yang sesuai.

Anda harus memeriksa artikel Permutasi di wikipeda. Juga, ada konsep bilangan Factoradic .

Bagaimanapun, masalah matematisnya cukup sulit.

Dalam C#Anda dapat menggunakan iterator, dan menghentikan penggunaan algoritma permutasi yield. Masalahnya adalah Anda tidak dapat bolak-balik, atau menggunakan file index.

Lebih banyak contoh algoritma permutasi untuk menghasilkannya.

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

1. Menggunakan Algoritma Fike, itu adalah salah satu yang paling cepat diketahui.
2. Menggunakan Algo to the Lexographic order.
3. Menggunakan nonlexographic, tetapi berjalan lebih cepat dari item 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.

fungsi permutasi di clojure.contrib.lazy_seqs sudah mengklaim melakukan hal ini.