Générer des permutations paresseusement

Je recherche un algorithme pour générer des permutations d'un ensemble de manière à pouvoir en faire une liste paresseuse dans Clojure. c'est-à-dire que je voudrais parcourir une liste de permutations où chaque permutation n'est pas calculée jusqu'à ce que je le demande, et toutes les permutations ne doivent pas être stockées en mémoire à la fois.

Sinon, je recherche un algorithme où, étant donné un certain ensemble, il retournera la permutation "suivante" de cet ensemble, de telle sorte que l'appel répété de la fonction sur sa propre sortie parcourra toutes les permutations de l'ensemble d'origine, en un certain ordre (quel est l'ordre n'a pas d'importance).

Existe-t-il un tel algorithme? La plupart des algorithmes générant des permutations que j'ai vus ont tendance à les générer tous à la fois (généralement de manière récursive), ce qui ne s'adapte pas à de très grands ensembles. Une implémentation dans Clojure (ou un autre langage fonctionnel) serait utile mais je peux la comprendre à partir du pseudocode.

Oui, il existe un algorithme de "prochaine permutation", et c'est assez simple aussi. La bibliothèque de modèles standard C ++ (STL) a même une fonction appelée next_permutation.

L'algorithme trouve en fait la permutation suivante - la suivante lexicographiquement. L'idée est la suivante: supposons qu'on vous donne une séquence, dites "32541". Quelle est la prochaine permutation?

Si vous y réfléchissez, vous verrez que c'est "34125". Et vos pensées étaient probablement quelque chose de ceci: dans "32541"

• il n'y a aucun moyen de garder le "32" fixe et de trouver une permutation ultérieure dans la partie "541", car cette permutation est déjà la dernière pour 5,4, et 1 - elle est triée par ordre décroissant.
• Vous devrez donc remplacer le "2" par quelque chose de plus grand - en fait, par le plus petit nombre plus grand que celui de la partie "541", à savoir 4.
• Maintenant, une fois que vous avez décidé que la permutation commencera par "34", le reste des nombres devrait être dans l'ordre croissant, donc la réponse est "34125".

L'algorithme consiste à implémenter précisément cette ligne de raisonnement:

1. Trouvez la plus longue «queue» qui est ordonnée par ordre décroissant. (La partie «541».)
2. Changez le nombre juste avant la queue (le "2") pour le plus petit nombre plus grand que celui de la queue (le 4).
3. Triez la queue par ordre croissant.

Vous pouvez faire (1.) efficacement en commençant par la fin et en reculant tant que l'élément précédent n'est pas plus petit que l'élément courant. Vous pouvez faire (2.) en échangeant simplement le "4" avec le "2", vous aurez donc "34521". Une fois que vous faites cela, vous pouvez éviter d'utiliser un algorithme de tri pour (3.), car la queue était, et est toujours (pensez à cela), triés par ordre décroissant, il suffit donc de l'inverser.

Le code C ++ fait précisément cela (regardez la source /usr/include/c++/4.0.0/bits/stl_algo.hsur votre système ou consultez cet article ); il devrait être simple de le traduire dans votre langue: [Lisez "BidirectionalIterator" comme "pointer", si vous n'êtes pas familier avec les itérateurs C ++. Le code retourne falses'il n'y a pas de permutation suivante, c'est-à-dire que nous sommes déjà dans l'ordre décroissant.]

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

Il peut sembler que cela peut prendre O (n) temps par permutation, mais si vous y réfléchissez plus attentivement, vous pouvez prouver que cela prend O (n!) Temps pour toutes les permutations au total, donc seulement O (1) - temps constant - par permutation.

La bonne chose est que l'algorithme fonctionne même lorsque vous avez une séquence avec des éléments répétés: avec, disons, "232254421", il trouverait la queue comme "54421", permuterait le "2" et le "4" (donc "232454221" ), inversez le reste, donnant "232412245", qui est la permutation suivante.

En supposant que nous parlons d'ordre lexicographique sur les valeurs permutées, il existe deux approches générales que vous pouvez utiliser:

1. transformer une permutation des éléments en permutation suivante (comme ShreevatsaR l'a posté), ou
2. calculez directement la nième permutation, en comptant nde 0 vers le haut.

Pour ceux (comme moi ;-) qui ne parlent pas c ++ en tant que natifs, l'approche 1 peut être implémentée à partir du pseudo-code suivant, en supposant l'indexation de base zéro d'un tableau d'index zéro sur la "gauche" (en remplaçant une autre structure , comme une liste, est "laissée comme exercice" ;-):

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

Voici un exemple commençant par une permutation actuelle 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

Pour la seconde approche (calcul direct de la nème permutation), rappelons qu'il existe des N!permutations d' Néléments. Par conséquent, si vous permutez des Néléments, les premières (N-1)!permutations doivent commencer par le plus petit élément, les (N-1)!permutations suivantes doivent commencer par le deuxième plus petit, et ainsi de suite. Cela conduit à l'approche récursive suivante (toujours en pseudo-code, en numérotant les permutations et les positions à partir de 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

Ainsi, par exemple, la 13e permutation d'ABCD se trouve comme suit:

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

Incidemment, la "suppression" d'éléments peut être représentée par un tableau parallèle de booléens qui indique quels éléments sont encore disponibles, il n'est donc pas nécessaire de créer un nouveau tableau à chaque appel récursif.

Donc, pour parcourir les permutations d'ABCD, comptez simplement de 0 à 23 (4! -1) et calculez directement la permutation correspondante.

Vous devriez consulter l' article Permutations sur wikipeda. Il y a aussi le concept de nombres factoradiques .

Quoi qu'il en soit, le problème mathématique est assez difficile.

Dans C#vous pouvez utiliser un iterator, et arrêter l'algorithme de permutation en utilisant yield. Le problème avec ceci est que vous ne pouvez pas aller et venir, ni utiliser un fichier index.

Plus d'exemples d'algorithmes de permutation pour les générer.

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

1. Utilise l'algorithme de Fike, qui est l'un des plus rapides connus.
2. Utilise l'Algo selon l'ordre lexographique.
3. Utilise le nonlexographique, mais s'exécute plus rapidement que l'élément 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.

la fonction permutations de clojure.contrib.lazy_seqs prétend déjà faire exactement cela.