Discussion :

[tagsOf]

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 c :

Sélectionner tout - Visualiser dans une fenêtre à part

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) ?

[Trap D]

Une recherche approfondie sur ce forum t'aurait donné la réponse : oui.

[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 !

[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

[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 ?

Merci encore !

[Zavonen]

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 python :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[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

[Zavonen]

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.

[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 !

PS:
Dans le genre (ici avec factorielle):

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

[tagsOf]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[tagsOf]

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

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Zavonen]

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 python :

Sélectionner tout - Visualiser dans une fenêtre à part

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()

[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ï

[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

[Trap D]

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

[tagsOf]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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

[Jedai]

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ï

[tagsOf]

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

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

[Trap D]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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