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)