84 votes

Génération de permutations paresseuses

Je cherche un algorithme pour générer les permutations d'un ensemble de telle sorte que je puisse en faire une liste paresseuse en Clojure. C'est-à-dire que j'aimerais itérer sur une liste de permutations où chaque permutation n'est pas calculée avant que je ne le demande, et où toutes les permutations n'ont pas besoin d'être stockées en mémoire en une seule fois.

Alternativement, je cherche un algorithme qui, étant donné un certain ensemble, renvoie la permutation "suivante" de cet ensemble, de telle sorte que l'appel répété de la fonction sur sa propre sortie fera défiler toutes les permutations de l'ensemble original, dans un certain ordre (l'ordre n'a pas d'importance).

Existe-t-il un tel algorithme ? La plupart des algorithmes de génération de permutations 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 n'est pas adapté aux très grands ensembles. Une implémentation en Clojure (ou un autre langage fonctionnel) serait utile, mais je peux me débrouiller à partir du pseudo-code.

135voto

ShreevatsaR Points 21219

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

L'algorithme trouve en fait le suivant la permutation -- celle qui est lexicographiquement la plus proche. L'idée est la suivante : supposons que l'on vous donne une séquence, disons "32541". Quelle est la permutation suivante ?

Si vous y réfléchissez, vous verrez que c'est "34125". Et vos pensées étaient probablement quelque chose comme ça : 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 lui dans 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, la réponse est donc "34125".

L'algorithme vise à mettre en œuvre précisément ce raisonnement :

  1. Trouvez la plus longue "queue" qui est classée par ordre décroissant. (La partie "541".)
  2. Changez le nombre juste avant la queue (le "2") en le plus petit nombre plus grand que lui dans la queue (le 4).
  3. Trier la queue par ordre croissant.

Vous pouvez réaliser (1.) efficacement en commençant par la fin et en revenant en arrière, tant que l'élément précédent n'est pas plus petit que l'élément actuel. Pour réaliser l'étape (2.), il suffit de remplacer le "4" par le "2", ce qui donne "34521". Une fois que vous avez fait cela, vous pouvez éviter d'utiliser un algorithme de tri pour (3.), parce que la queue était, et est toujours (pensez-y), triée par ordre décroissant, donc il suffit de l'inverser.

C'est précisément ce que fait le code C++ (voir le code source dans la section /usr/include/c++/4.0.0/bits/stl_algo.h sur votre système, ou voir cet article ) ; il devrait être simple de le traduire dans votre langue : [Lire "BidirectionalIterator" comme "pointeur", si vous n'êtes pas familier avec les itérateurs C++. Le code renvoie false s'il n'y a pas de permutation suivante, c'est-à-dire que nous sommes déjà en 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 puisse 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.

Ce qui est bien, c'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", échangerait le "2" et le "4" (donc "232454221"), inverserait le reste, ce qui donnerait "232412245", qui est la permutation suivante.

42voto

joel.neely Points 17059

En supposant que nous parlons d'un 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 l'a indiqué ShreevatsaR), ou bien
  2. calculer directement le n e permutation, tout en comptant n à partir de 0.

Pour ceux (comme moi ;-) qui ne sont pas natifs en c++, l'approche 1 peut être implémentée à partir du pseudo-code suivant, en supposant une indexation basée sur zéro d'un tableau avec l'index zéro à "gauche" (la substitution d'une autre structure, telle qu'une liste, est "laissée en 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 à partir d'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 e permutation), rappelez-vous qu'il existe N! permutations de N éléments. Par conséquent, si vous permutez N les premiers éléments (N-1)! les permutations doivent commencer par le plus petit élément, le suivant (N-1)! les permutations doivent commencer par la deuxième plus petite, et ainsi de suite. Cela conduit à l'approche récursive suivante (à nouveau 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 de ABCD est trouvée 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

Par ailleurs, 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.

Ainsi, pour itérer parmi les permutations de ABCD, il suffit de compter de 0 à 23 (4!-1) et de calculer directement la permutation correspondante.

3voto

Bogdan Maxim Points 2365

Vous devez vérifier le Article sur les permutations sur wikipeda. Il y a aussi le concept de Factoradic numéros.

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

Sur C# vous pouvez utiliser un iterator et arrêter l'algorithme de permutation en utilisant yield . Le problème, c'est qu'il n'est pas possible de faire des allers-retours, ni d'utiliser une carte à puce. index .

3voto

Autres 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 à l'ordre lexographique.

  3. Utilise le non-lexographique, mais fonctionne plus rapidement que le point 2.

  4. 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.

  5. 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.

  6. 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.

2voto

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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X