Generare pigramente permutazioni

Question

Sto cercando un algoritmo per generare permutazioni di un set in modo tale da poterne fare un elenco pigro in Clojure.cioè.Vorrei scorrere un elenco di permutazioni in cui ciascuna permutazione non viene calcolata finché non la richiedo e tutte le permutazioni non devono essere archiviate in memoria contemporaneamente.

In alternativa, sto cercando un algoritmo in cui, dato un certo set, restituirà la permutazione "successiva" di quel set, in modo tale che chiamando ripetutamente la funzione sul proprio output scorreranno tutte le permutazioni del set originale, in un po' di ordine (quale sia l'ordine non ha importanza).

Esiste un algoritmo del genere?La maggior parte degli algoritmi di generazione di permutazioni che ho visto tendono a generarli tutti in una volta (di solito in modo ricorsivo), il che non si adatta a insiemi molto grandi.Un'implementazione in Clojure (o un altro linguaggio funzionale) sarebbe utile, ma posso capirlo dallo pseudocodice.

Answer 1

Sì là È un algoritmo di "prossima permutazione", ed è anche abbastanza semplice.La libreria di modelli standard (STL) C++ ha anche una funzione chiamata next_permutation.

L'algoritmo trova effettivamente il file Prossimo permutazione: quella lessicograficamente successiva.L'idea è questa:supponiamo che ti venga data una sequenza, ad esempio "32541".Qual è la prossima permutazione?

Se ci pensi, vedrai che è "34125".E i tuoi pensieri probabilmente erano qualcosa del genere:In "32541",

• non c'è modo di mantenere fisso il "32" e trovare una permutazione successiva nella parte "541", perché quella permutazione è già l'ultima per 5,4 e 1 -- è ordinata in ordine decrescente.
• Quindi dovrai cambiare il "2" con qualcosa di più grande - in effetti, con il numero più piccolo più grande di quello nella parte "541", vale a dire 4.
• Ora, una volta deciso che la permutazione inizierà con "34", il resto dei numeri dovrebbe essere in ordine crescente, quindi la risposta è "34125".

L’algoritmo deve implementare proprio questo ragionamento:

1. Trova la "coda" più lunga ordinata in ordine decrescente.(La parte "541".)
2. Cambia il numero appena prima della coda (il "2") con il numero più piccolo e più grande di quello nella coda (il 4).
3. Ordina la coda in ordine crescente.

Puoi fare (1.) in modo efficiente iniziando dalla fine e andando indietro purché l'elemento precedente non sia più piccolo dell'elemento corrente.Puoi fare (2.) semplicemente scambiando il "4" con il "2", così avrai "34521".Una volta fatto questo, puoi evitare di usare un algoritmo di ordinamento per (3.), perché la coda era, ed è ancora (pensaci), ordinata in ordine decrescente, quindi deve solo essere invertita.

Il codice C++ fa esattamente questo (guarda il sorgente in /usr/include/c++/4.0.0/bits/stl_algo.h sul tuo sistema, o vedere Questo articolo);dovrebbe essere semplice tradurlo nella tua lingua:[Leggi "BidirectionIterator" come "puntatore", se non hai familiarità con gli iteratori C++.Il codice ritorna false se non c'è nessuna permutazione successiva, cioèsiamo già in ordine decrescente.]

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

Potrebbe sembrare che possa occorrere O(n) tempo per permutazione, ma se ci pensi più attentamente, puoi dimostrare che occorre O(n!) tempo per tutte le permutazioni in totale, quindi solo O(1) -- tempo costante - per permutazione.

La cosa buona è che l'algoritmo funziona anche quando hai una sequenza con elementi ripetuti:con, diciamo, "232254421", troverebbe la coda come "54421", scambierebbe "2" e "4" (quindi "232454221"), invertirebbe il resto, dando "232412245", che è la permutazione successiva.

Answer 2

Supponendo che stiamo parlando di un ordine lessicografico sui valori permutati, ci sono due approcci generali che puoi usare:

1. trasforma una permutazione degli elementi nella permutazione successiva (come pubblicato da ShreevatsaR), oppure
2. calcola direttamente la n th permutazione, contando N! da 0 in su.

Per quelli (come me ;-) che non parlano c ++ come nativi, l'approccio 1 può essere implementato dal seguente pseudo-codice, assumendo l'indicizzazione a base zero di un array con indice zero sulla quotazione &; & sinistra quot; (sostituendo qualche altra struttura, come un elenco, è " lasciato come esercizio " ;-):

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

Ecco un esempio che inizia con una permutazione corrente di 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

Per il secondo approccio (calcolo diretto della N th permutazione), ricorda che ci sono (N-1)! permutazioni di <=> elementi. Pertanto, se si stanno permutando <=> elementi, le prime <=> permutazioni devono iniziare con l'elemento più piccolo, le successive <=> permutazioni devono iniziare con il secondo più piccolo e così via. Questo porta al seguente approccio ricorsivo (sempre in pseudo-codice, numerando le permutazioni e le posizioni da 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

Quindi, ad esempio, la tredicesima permutazione di ABCD si trova come segue:

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

Per inciso, la " rimozione " di elementi può essere rappresentato da un array parallelo di booleani che indica quali elementi sono ancora disponibili, quindi non è necessario creare un nuovo array su ogni chiamata ricorsiva.

Quindi, per scorrere le permutazioni di ABCD, basta contare da 0 a 23 (4! -1) e calcolare direttamente la permutazione corrispondente.

Answer 3

Dovresti controllare Articolo sulle permutazioni su wikipeda. Inoltre, esiste il concetto di Factoradic .

Comunque, il problema matematico è piuttosto difficile.

In C# puoi usare un iterator e fermare l'algoritmo di permutazione usando yield. Il problema è che non puoi andare avanti e indietro o usare un index.

Answer 4

Altri esempi di algoritmi di permutazione per generarli.

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

1. Utilizza l'algoritmo di Fike, quello più conosciuto.
2. Usa l'Algo nell'ordine Lexografico.
3. Utilizza il nonlexografico, ma corre più veloce dell'articolo 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.

Answer 5

la funzione permutazioni in clojure.contrib.lazy_seqs afferma già di fare proprio questo.