algorithm - Generando permutaciones perezosamente

functional-programming clojure

Question

Estoy buscando un algoritmo para generar permutaciones de un conjunto de tal manera que pueda hacer una lista perezosa de ellos en Clojure. es decir, me gustaría iterar sobre una lista de permutaciones donde cada permutación no se calcula hasta que lo solicite, y todas las permutaciones no tienen que almacenarse en la memoria a la vez.

Alternativamente, estoy buscando un algoritmo en el que, dado un determinado conjunto, devuelva la "siguiente" permutación de ese conjunto, de tal manera que llamar repetidamente a la función en su propia salida recorra todas las permutaciones del conjunto original, en un poco de orden (lo que es el orden no importa).

¿Hay tal algoritmo? La mayoría de los algoritmos de generación de permutación que he visto tienden a generarlos todos a la vez (por lo general de forma recursiva), que no se ajusta a conjuntos muy grandes. Una implementación en Clojure (u otro lenguaje funcional) sería útil, pero puedo resolverlo desde un pseudocódigo.

Answer 1

Deberías consultar el artículo de Permutations en wikipeda. Además, existe el concepto de números Factoradic .

De todos modos, el problema matemático es bastante difícil.

En C# puede usar un iterator y detener el algoritmo de permutación usando yield . El problema con esto es que no puedes ir y venir, o usar un index .

Answer 2

Más ejemplos de algoritmos de permutación para generarlos.

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

1. Utiliza el algoritmo de Fike, que es el más rápido conocido.
2. Utiliza el Algo para el orden Lexográfico.
3. Utiliza el nonlexographic, pero funciona más rápido que el 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.

Answer 3

Suponiendo que estamos hablando de un orden lexicográfico sobre los valores que se permutan, hay dos enfoques generales que puede usar:

1. transformar una permutación de los elementos en la siguiente permutación (como publicó ShreevatsaR), o
2. calcula directamente la n ésima permutación, mientras cuentas n desde 0 hacia arriba.

Para aquellos (como yo ;-) que no hablan c ++ como nativos, el enfoque 1 puede implementarse a partir del siguiente pseudocódigo, asumiendo la indexación basada en cero de una matriz con índice cero en la "izquierda" (sustituyendo alguna otra estructura) , como una lista, es "dejado como un ejercicio" ;-):

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

Aquí hay un ejemplo que comienza con una permutación actual de 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

Para el segundo enfoque (cálculo directo de la n th permutación), recuerde que hay N! permutaciones de N elementos. Por lo tanto, si permuta N elementos, ¡el primero (N-1)! las permutaciones deben comenzar con el elemento más pequeño, el siguiente (N-1)! las permutaciones deben comenzar con la segunda más pequeña, y así sucesivamente. Esto lleva al siguiente enfoque recursivo (nuevamente en pseudocódigo, numerando las permutaciones y posiciones desde 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

Entonces, por ejemplo, la decimotercera permutación de ABCD se encuentra de la siguiente manera:

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

Incidentalmente, la "eliminación" de elementos se puede representar mediante una matriz paralela de booleanos que indica qué elementos están todavía disponibles, por lo que no es necesario crear una nueva matriz en cada llamada recursiva.

Entonces, para iterar a través de las permutaciones de ABCD, simplemente cuente de 0 a 23 (4! -1) y calcule directamente la permutación correspondiente.

Answer 4

la función de permutaciones en clojure.contrib.lazy_seqs ya afirma hacer justamente esto.

Answer 5

Sí, hay un algoritmo de "próxima permutación", y es bastante simple también. La biblioteca de plantillas estándar (STL) de C ++ incluso tiene una función llamada next_permutation .

El algoritmo realmente encuentra la siguiente permutación, la siguiente lexicográficamente. La idea es esta: supongamos que le dan una secuencia, digamos "32541". ¿Cuál es la próxima permutación?

Si lo piensas bien, verás que es "34125". Y sus pensamientos fueron probablemente algo así: en "32541",

• no hay forma de mantener el "32" fijo y encontrar una permutación posterior en la parte "541", porque esa permutación ya es la última para 5,4, y 1 - está ordenada en orden decreciente.
• Por lo tanto, tendrá que cambiar el "2" a algo más grande, de hecho, al número más pequeño que en la parte "541", es decir, 4.
• Ahora, una vez que haya decidido que la permutación comenzará como "34", el resto de los números debería estar en orden creciente, por lo que la respuesta es "34125".

El algoritmo es implementar precisamente esa línea de razonamiento:

1. Encuentra la "cola" más larga que se ordena en orden decreciente. (La parte "541")
2. Cambie el número justo antes de la cola (el "2") al número más pequeño más grande que en la cola (el 4).
3. Clasifica la cola en orden creciente.

Puede hacer (1.) de manera eficiente comenzando por el final y retrocediendo siempre que el elemento anterior no sea más pequeño que el elemento actual. Puedes hacer (2.) simplemente cambiando el "4" por el "2", así tendrás "34521". Una vez hecho esto, puedes evitar usar un algoritmo de clasificación para (3.), porque la cola fue, y todavía está (piénselo), ordenado en orden decreciente, por lo que solo debe revertirse.

El código C ++ hace precisamente esto (mira la fuente en /usr/include/c++/4.0.0/bits/stl_algo.h en tu sistema, o mira este artículo ); debería ser simple traducirlo a su idioma: [Lea "BidirectionalIterator" como "puntero", si no está familiarizado con los iteradores de C ++. El código devuelve false si no hay próxima permutación, es decir, ya estamos en orden decreciente.]

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

Puede parecer que puede tomar O (n) tiempo por permutación, pero si lo piensa con más cuidado, puede probar que toma O (n!) El tiempo para todas las permutaciones en total, por lo que solo O (1) - tiempo constante - por permutación.

Lo bueno es que el algoritmo funciona incluso cuando tienes una secuencia con elementos repetidos: con, digamos, "232254421", encontraría la cola como "54421", cambiar el "2" y "4" (así que "232454221" ), invierta el resto, dando "232412245", que es la siguiente permutación.