Générer des permutations paresseusement

Je cherche un algorithme pour générer des permutations d’un ensemble de manière à pouvoir en faire une liste paresseuse dans Clojure. c.-à-d. 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 immédiatement.

Sinon, je cherche un algorithme où, à partir d’un certain ensemble, il retournera la permutation “suivante” de cet ensemble, de sorte que l’appel répété de la fonction sur sa propre sortie fera défiler toutes les permutations de l’ensemble d’origine. un peu d’ordre (peu importe l’ordre).

Y a-t-il un tel algorithme? La plupart des algorithmes générateurs de permutation que j’ai vus ont tendance à les générer tous en même temps (généralement de manière récursive), ce qui ne correspond pas à de très grands ensembles. Une implémentation en Clojure (ou un autre langage fonctionnel) serait utile mais je peux le comprendre à partir d’un pseudocode.

Oui, il y a 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 effectivement la prochaine permutation – la suivante lexicographiquement. L’idée est la suivante: supposons que l’on vous donne une séquence, disons “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 pas 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 sortingée par ordre décroissant.
  • Donc, vous devrez changer le “2” en quelque chose de plus grand – en fait, au plus petit nombre plus grand que dans la partie “541”, à savoir 4.
  • Maintenant, une fois que vous avez décidé que la permutation commencera par “34”, le rest des nombres devrait être en ordre croissant, donc la réponse est “34125”.

L’algorithme doit 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. Changer le nombre juste avant la queue (le “2”) au plus petit nombre plus grand que dans la queue (le 4).
  3. Trier la queue dans l’ordre croissant.

Vous pouvez faire (1.) efficacement en commençant à la fin et en reculant tant que l’élément précédent n’est pas plus petit que l’élément actuel. 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 sorting pour (3.), car la queue était, et est toujours (pensez à cela), sortingé par ordre décroissant, il suffit donc de l’inverser.

Le code C ++ fait précisément cela (regardez la source dans /usr/include/c++/4.0.0/bits/stl_algo.h sur votre système, ou consultez cet article ); il devrait être simple de le traduire dans votre langue: [Lire “BidirectionalIterator” en tant que “pointeur”, si vous n’êtes pas familier avec les iterators C ++. Le code retourne false s’il n’y a pas de permutation suivante, c’est-à-dire que nous sums déjà en ordre décroissant.]

 template  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 du temps O (n) par permutation, mais si vous y réfléchissez plus attentivement, vous pouvez prouver qu'il faut O (n!) Temps pour toutes les permutations, 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, par exemple, "232254421", il trouverait la queue comme "54421", échangez les "2" et "4" (donc "232454221" ), inverser le rest en donnant "232412245", qui est la prochaine permutation.

En supposant que nous parlions de l’ordre lexicographique sur les valeurs permutées, vous pouvez utiliser deux approches générales:

  1. transformer une permutation des éléments à la prochaine permutation (comme l’a affiché ShreevatsaR), ou
  2. calculer directement la nième permutation, en comptant n de 0 à la hausse.

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 une indexation à base zéro d’un tableau avec un index zéro sur la “gauche” , comme une liste, est “laissé comme un 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 (ie positions 2..3) gives CBAD 5. CBAD is the next permutation after CADB 

Pour la deuxième approche (calcul direct de la n ième permutation), rappelez-vous qu’il y a N! permutations de N éléments. Par conséquent, si vous permutez N éléments, le premier (N-1)! les permutations doivent commencer par le plus petit élément, le suivant (N-1)! les permutations doivent commencer par le deuxième plus petit, et ainsi de suite. Cela conduit à l’approche récursive suivante (là encore en pseudo-code, 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 13ème permutation de 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” des é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 de ABCD, il suffit de compter de 0 à 23 (4! -1) et de calculer directement la permutation correspondante.

Vous devriez vérifier l’ article sur les permutations sur wikipeda. Il y a aussi le concept de nombres factoriels .

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

En C# vous pouvez utiliser un iterator et arrêter l’algorithme de permutation en utilisant le yield . Le problème avec ceci est que vous ne pouvez pas aller-retour, ou utiliser un 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, celui qui est le plus rapide connu.
  2. Utilise l’Algo dans l’ordre Lexographic.
  3. Utilise le non-graphique, mais s’exécute plus vite que le point 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 JS 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; 

PROGRAM TestLexPerms; CONST marksize = 5; VAR marks : ARRAY [1..marksize] OF INTEGER; ii : INTEGER; permcount : INTEGER;

PROCEDURE WriteArray;
VAR i: ENTIER;
COMMENCER
POUR i: = 1 est marqué
DO écrire;
nombre permcount: = permcount + 1;
WriteLn;
FIN;

PROCÉDURE LexPerm;
{Produit des permutations dans l’ordre lexicographique. Les marques de tableau sont globales}
{et a n ou moins de marques. La procédure WriteArray () est globale et}
{affiche les résultats. }
VAR
travail: ENTIER:
mp, hlen, i: ENTIER;
COMMENCER
SI
ALORS COMMENCER {Echangez la paire}
travail: = marques [1];
marques [1]: = marques [2];
marques [2]: = travail;
WriteArray;
FIN
AUTRE COMMENCE
POUR mp: = DOWNTO 1
COMMENCEZ
LexPerm <>;
hlen: = DIV 2;
POUR i: = 1 TO hlen
COMMENCEZ {Un autre échange}
travail: = marques [i];
marques [i]: = marques [n – i];
marques [n – i]: = travail
FIN;
travail: = marques [n]; {Plus d’échange}
marques [n [: = marques [mp];
marques [mp]: = work;
WriteArray;
FIN;
LexPerm <>
FIN;
FIN;

COMMENCER {Main}
POUR ii: = 1 est marqué
Marques d’OD [ii]: = ii;
compte permanent: = 1; {La position de départ est la permutation}
WriteLn ;
WriteLn
LexPerm;
WriteLn ;
ReadLn;
FIN.

3.

 PROGRAM TestAllPerms; CONST marksize = 5; VAR marks : ARRAY [1..marksize] of INTEGER; ii : INTEGER; permcount : INTEGER; 

PROGRAM TestAllPerms; CONST marksize = 5; VAR marks : ARRAY [1..marksize] of INTEGER; ii : INTEGER; permcount : INTEGER;

PROCEDURE WriteArray;
VAR i: ENTIER;
COMMENCER
POUR i: = 1 est marqué
DO écrire;
WriteLn;
nombre permcount: = permcount + 1;
FIN;

PROCÉDURE AllPerm (n: INTEGER);
{Donne des permutations dans un ordre non-flexicographique. Les marques de tableau sont}
{global et a peu ou pas de marques. La procédure WriteArray est globale et}
{affiche les résultats. }
VAR
travail: INTEGER;
mp, swaptemp: INTEGER;
COMMENCER
SI
ALORS COMMENCER {Echangez la paire}
travail: = marques [1];
marques [1]: = marques [2];
marques [2]: = travail;
WriteArray;
FIN
AUTRE COMMENCE
POUR mp: = DOWNTO 1
COMMENCEZ
ALLPerm << n - 1 >>;
SI>
PUIS swaptemp: = 1
ELSE swaptemp: = mp;
travail: = marques [n];
marques [n]: = marques [swaptemp};
marques [swaptemp}: = work;
WriteArray;
AllPerm ;
FIN;
FIN;

COMMENCER {Main}
POUR ii: = 1 est marqué
Marques DO [ii]: = ii
compte permanent: = 1;
WriteLn ;
WriteLn;
Allperm ;
WriteLn ;
ReadLn;
FIN.

La fonction de permutations dans clojure.consortingb.lazy_seqs prétend déjà faire exactement cela.