Algorithme de permutation

Version imprimable

Salut à tous,

Presque tout est dans le titre, je n'arrive pas à comprendre cette algorthme en regardant les sources suivantes (qui fonctionnent parfaitement en passant) ...

J'aimerai beaucoup que l'on m'explique le principe de l'algo, j'ai besoin de le comprendre pour essayer de le coder plus clairement si cela est possible, je vous remercie d'avance !!
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <stdio.h> #define NB_VAL 3 int array[NB_VAL] = { 0 }; int num = 0; void display() { int i; for ( i = 0; i < NB_VAL; ++i ) printf( "%d ", array[i] ); printf("\n" ); } void permutation( int index ) { int i; array[++index] = ++num; if ( num == NB_VAL ) display(); for ( i = 0; i < NB_VAL; ++i ) if ( !array[i] ) permutation( i-1 ); array[index] = 0; --num; } int main() { int i; for ( i = -1; i < NB_VAL-1; ++i ) permutation( i ); }
Dans l'exemple précis seront affichés toutes les permutation de 1,2,3...

Merci d'avance !

De manière générale, existe t'il un algorithme qui a partir d'une liste ou d'un tableau d'entier, affiche toutes les permutations de ces entiers (en supposant que les entiers soit différents) ?

07/03/2008, 13h49
Trap D

Une recherche approfondie sur ce forum t'aurait donné la réponse : oui.
07/03/2008, 14h02
tagsOf

Effectivement j'en ai trouvé plusieurs dont un en java par ici.

Mais le problème reste entier, je n'arrive pas à comprendre les mécanismes de l'algo, je vois ce qui se passe mais pas pourquoi...

Saurai tu m'expliquer en français comment fonctionne le principe de cet algorithme, je t'en remercierai !
07/03/2008, 18h10
acx01b

une permutation d'un ensemble E:
c'est un n-upplet qui commence par x1 suivi d'une permutation de E privé de x1
ou un n-upplet qui commence par x2 suivi d'une permutation de E privé de x2
ou un n-upplet qui commence par x3 suivi d'une permutation de E privé de x3
...
ou un n-upplet qui commence par xn suivi d'une permutation de E privé de xn

où x1, x2, x3 .... xn sont les éléments de E
07/03/2008, 20h17
tagsOf

Je te remercie, c'est ce genre de réponse que j'attendais avec impatience, donc cela semble montrer que ca se code généralement de manière récursive, tu le coderai de manière similaire au code proposée au dessus ?

:king: Merci encore !

Dans une autre discussion http://www.developpez.net/forums/sho...62&postcount=8
j'ai proposé un algo itératif basé sur les cycles pour générer toutes les permutations, en voici une version plus récente (Python)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# -*- coding: cp1252 -*-
# une méthode itérative pour générer le groupe symétrique
 
#cycle opérant sur les p derniers éléments
def cycle (n,p):
    L1=range(0,n-p)
    L2=[i+1 for i in range(n-p,n-1)]
    return L1+L2+[n-p]
 
# composée de 2 permutations
def compose (P1,P2):
    return [P2[P1[i]] for i in range(0,len(P1))]
 
# puissance d'une permutation
def puissance (P,n):
    PUISS=range(0,len(P))
    for i in range(0,n):
        PUISS=compose(PUISS,P)
    return PUISS
 
# générer toutes les permutations
def permutations (n):
    CYCLES=[cycle(n,2+i) for i in range(0,n-1)]
    PERM1=[cycle(n-1,0)]
    for i in range (0,n-1):
        PERM2=[compose(PERM1[k],puissance(CYCLES[i],j)) for j in range(0,i+2) for k in range(0,len(PERM1))]
        PERM1=PERM2
    return PERM2
 
#programme principal
print permutations(5)

07/03/2008, 23h03
tagsOf

Je te remercie de ta contribution !

Seulement moi et python on est pas très amis ^^'
Tu as écris le code en un autre langage proche du C/C++ ?

Merci encore :king:
08/03/2008, 07h28
Zavonen

Citation:

Tu as écris le code en un autre langage proche du C/C++ ?

Non, mais l'algo est décrit en français sur la page référencée.
08/03/2008, 08h49
tagsOf

Tu fais aussi allusion a la manière récursive de coder cela (comme mon code ci dessus), tu pourrais essayer de me l'expliquer en français "a ta manière récursive" pour voir si j'arriverai peut être a comprendre cela, je te remercie encore !:king:

PS:
Dans le genre (ici avec factorielle):

factorielle (1) = 1
factorielle (n) = n x factorielle (n-1)

J'ai trouver cette algo, cependant je ne sais pas si il est juste, et je ne comprend la ligne en rouge, si vous voyez des fautes, ou souhaitez y apporter quelque corrections ou éclaircissement, n'hésitez pas !
Code:

1 2 3 4 5 6 7 8 9 10 11 fonction permut (tableau) /* ou un pointeur */ foreach a in tableau do print a sous_tableau=tableau - element_a if sous_tableau=1case /* test de fin de recurtion */ then print sous_tableau[0]+cr/lf else permut(sous_tableau) /* recurtion */ end if end for end fonction

Je viens d'implémenter l'algorithme si dessus en C, ca donne ca :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
int array[3]={1,2,3};
 
 
int* sousTableau(int indice, int * tableau, int N){
  int curseur=0;
  int *sous_tableau=malloc( (N-1)*sizeof(*sous_tableau) );
  assert(sous_tableau);
 
  for(int i=0; i<N; i++)
    if( i != indice ){
      sous_tableau[curseur]=tableau[i];
      curseur++;
    }
  return sous_tableau;
}
 
void permutation(int * tableau, int N){
  int * sous_tableau=NULL;
 
  for(int i=0; i < N; i++)
    {
      printf("%d ",tableau[i]);
      sous_tableau=sousTableau(i,tableau,N);
      if( N == 2){
    printf("%d ",sous_tableau[0]);
    printf("\n");
      }
      else
    permutation(sous_tableau, N-1);
   }
 
}
 
int main(void){
  permutation(array,3);
  return EXIT_SUCCESS;
}

Lors de l'exécution, j'obtiens ce résultat inattendu:

1 2 3
3 2
2 1 3
3 1
3 1 2
2 1

Voyez vous les erreurs, dans mon code comme dans mon algo ?

Merci d'avance :king:

Excuse, c'est encore du serpent, mais c'est abondamment commenté (en français)
Si tu tiens vraiment au récursif et à exploser des piles (n! ça croit ..achement vite)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: cp1252 -*-
import copy
 
 
# ensemble des permutations de la liste L
def permutations (L):
    if len(L)==1: # cas où il n'y a qu'un seul élément
        return [L] # une seule permutation
    X=L[0] # sinon en récupère le premier élément
    L1=L[1:len(L)] # et on l'élimine de L
    L2=permutations(L1) # appel récursif
    L4=[] # pour recevoir le résultat
    for L3 in L2: # on parcourt toutes les permutations de la queue de liste
        for i in range(0,len(L3)+1): # on fait circuler le premier élément
            L5=copy.deepcopy(L3) #L5 est un clone de L3
            L5.insert(i,X) # on place X au bon endroit
            L4.insert(0,L5)# et on enrichit L4
    return L4
 
def main():
    print permutations([0, 1, 2,3])
 
if __name__ == '__main__':
    main()

08/03/2008, 10h17
Jedai

Même en récursif, et sauf à coder une abomination, ta pile ne prendra que n appels maximum empilés. (Ce qui n'est pas génial, sûr, d'un autre côté vu que le nombre de permutation croit effectivement en n!, essayer d'appliquer permutation à une liste suffisamment grande pour faire exploser ta pile est une bonne recette pour attendre la mort thermique de l'univers...)

Le code envoyé par Zavonen adopte l'optique que les permutations de (x1,x2,...,xn) sont l'ensemble des permutations de (x2,...,xn) dans lequel on rajoute x1 à toutes les positions possibles.
Une autre vision fréquemment adoptée est que les permutations de (x1,x2,...,xn) sont l'ensemble des permutations commençant par xk (pour k dans [1..n]) et suivi par toutes les permutations possibles de (x1,..,xn) privé de xk.

--
Jedaï
08/03/2008, 10h31
tagsOf

Je vous remercie j'arrive à comprendre l'algo en python, autrement pour revenir à l'algo en francais que j'ai posé au dessus, vous y voyez une erreur ou bien est-ce dans mon implémentation en C qu'il y a des horreurs ?

Merci encore :king:
08/03/2008, 11h50
Trap D

Pourquoi fais-tu un cas particulier pour N == 2 ?

Citation:

Envoyé par Trap D

Pourquoi fais-tu un cas particulier pour N == 2 ?

Alors j'ai betement implémenter l'algorithme et en particulier la ligne en rouge:
Code:

1 2 3 4 5 6 7 8 9 10 11 fonction permut (tableau) /* ou un pointeur */ foreach a in tableau do print a sous_tableau=tableau - element_a if sous_tableau=1case /* test de fin de recurtion */ then print sous_tableau[0]+cr/lf else permut(sous_tableau) /* recurtion */ end if end for end fonction
Or si N==2, taille du tableau = 2 alors celle du sous_tableau sera égale à 1.

N'hesite pas à me poser d'autre question, je te remercie de ton intervention :king:

08/03/2008, 19h03
benDelphic

oh lala j espere que mon prof d optimisation combinatoire ne visite pas ce forum... il aurait fait tout une discussion dessus...
pour résumer ton algorithme est de type EXPONENTIEL...si tu ne limite pas l etendue de ta chaine de depart l algorithme va s'eterniser.
en fait une permutation n'est qu'un element d'un enssemble issu par un N-produit cartesien d'un ensemble de depart sans répétition... jusqu'a aujourd hui on ne dispose pas d'algorithmes efficaces pour le faire...et il ne peut -peut etre pas - y avoir d algorithmes resolvant ce pb car pour une sequance de n nombre il y a 2^n permutation!!! ce n est pas important le nombre d iteration que tu vas faire pour trouver ces permutations mais plutot c'est le nbr d element a lister:mrgreen:
08/03/2008, 20h41
Jedai

Citation:

Envoyé par benDelphic

en fait une permutation n'est qu'un element d'un enssemble issu par un N-produit cartesien d'un ensemble de depart sans répétition... jusqu'a aujourd hui on ne dispose pas d'algorithmes efficaces pour le faire...et il ne peut -peut etre pas - y avoir d algorithmes resolvant ce pb car pour une sequance de n nombre il y a 2^n permutation!!!

Non, il y en a n!, 2^n est le nombre de parties d'un ensemble à n éléments. n! est bien pire que 2^n et devient bien vite trop grand pour stocker toutes les permutations en mémoire. C'est pourquoi il est préférable d'énumérer les permutations sans les stocker (ce qu'on peut faire récursivement ou itérativement).

--
Jedaï
08/03/2008, 22h57
tagsOf

Citation:

Envoyé par benDelphic

pour résumer ton algorithme est de type EXPONENTIEL...

:roll: Euh, tu ne m'apprend rien de nouveau, j'ai pas lancé ce fil pour découvrir un algorithme révolutionnaire, mais pouvoir implémenter plus facilement l'algorithme récursif.

Je te remercie tout de même pour ta contribution :king:

Code:

1
2
3
4
5
6
7
8
9
10
fonction permut (tableau) /* ou un pointeur */ 
 foreach a in tableau do 
  	print a 
  	sous_tableau=tableau - element_a 
  	if sous_tableau=1case /* test de fin de recurtion */ 
  		then print sous_tableau[0]+cr/lf 
  	else permut(sous_tableau) /* recurtion */ 
  	end if 
 end for 
end fonction

Cet algo est faux, il suffit de le dérouler à la main

allons-y avec tableau = 1,2,3

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
fonction permut ([1,2,3])
  pour chaque élément a de [1,2,3]
    ecrire a                                   ==> 1
	// le tableau n'a pas une case donc
	fonction permut([2 ,3])
	  pour chaque element a de [2,3]
	    ecrire a                           ==> 2
		le tableau a 2 cases donc
        print sous_tableau[0]+cr/lf 	       ==> 2 \n  => à l'écran 1 2 2  
		ecrire a                       ==> 3
		le tableau a 2 cases donc
        print sous_tableau[0]+cr/lf 	       ==> 2 \n  => à l'écran 3 2 \n
	  fin for
	fin fonction permut
	ecrire a                               ==> 2
	fonction permut([1,3])
	  pour chaque element a de [1,3]
	    ecrire a                           ==> 1
		le tableau a 2 cases donc
        print sous_tableau[0]+cr/lf 	       ==> 1 \n  => à l'écran 2 1 1 \n 
		ecrire a                       ==> 3
		le tableau a 2 cases donc
        print sous_tableau[0]+cr/lf 	       ==> 1 \n  => à l'écran 1 3 \n
	  fin for
	fin fonction permut
	ecrire a                               ==> 3
	fonction permut([1,2])
	  pour chaque element a de [1,2]
	    ecrire a                           ==> 1
		le tableau a 2 cases donc
        print sous_tableau[0]+cr/lf 	       ==> 1 \n  => à l'écran 3 1 1 \n 
		ecrire a                       ==> 2
		le tableau a 2 cases donc
        print sous_tableau[0]+cr/lf 	       ==> 1 \n  => à l'écran 2 1\n
	  fin for
	fin fonction permut
fin fonction permut

J'ai peut-être fait des erreurs mais on se rend tout de même compte tout de suite qu'il est faux car lorsque le tableau a 3 éléments, on n'écrit qu'une seule fois le premier élément alors qu'il y a 2 permutatations qui commencent pas cet élément.
En ce qui concerne le code C, tu as de nombreuses fuites mémoire puisqu'aucun free n'est fait alors que tu as de nombreux malloc.
Tu peux passer en paramètre des fonction la permutation en cours de construction et le reste du tableau à travailler

Je vais être un peu plus explicite sur la fonction permutation

Code:

1
2
3
4
5
6
7
8
9
10
11
12
fonction permutation(tableau, permutation)
debut
  si tableau est vide alors
    afficher la permutation
  sinon
    pour tous les éléments a du tableau faire
      tableau1 <- tableau - a
      permuation1 <- permutation + a
      permutation(tableau1, permutation1)
    fin pour
  fin si
fin

09/03/2008, 22h23
tagsOf

:yaisse2:

Je te remercie, c'est exactement ce que j'attendais, y a tout en français et en plus c'est très claire :mrgreen:! Je met le fil en résolu, encore un grand merci ! :king: