Algorithme de permutation

Signaler
Messages postés
8
Date d'inscription
samedi 7 août 2004
Statut
Membre
Dernière intervention
8 mars 2008
-
Messages postés
35
Date d'inscription
mardi 7 novembre 2006
Statut
Membre
Dernière intervention
18 septembre 2009
-
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 !!


...................................

#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 );
}

</stdio.h>
A voir également:

7 réponses

Messages postés
8
Date d'inscription
samedi 7 août 2004
Statut
Membre
Dernière intervention
8 mars 2008

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


#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 );
}
Messages postés
482
Date d'inscription
vendredi 26 août 2005
Statut
Membre
Dernière intervention
5 décembre 2009
1
Tous les arrangements de NB_VAL objets (3 ici) = factorielle(NB_VAL) lignes éditées (6 ici).

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

Jean-François
Messages postés
8
Date d'inscription
samedi 7 août 2004
Statut
Membre
Dernière intervention
8 mars 2008

J'ai bien compris ce que le programme faisait jfrancois, ce que j'aimerais comprendre c'est le principe de l'algo ...
Messages postés
8
Date d'inscription
samedi 7 août 2004
Statut
Membre
Dernière intervention
8 mars 2008

Pas d'idée ?
Messages postés
8
Date d'inscription
samedi 7 août 2004
Statut
Membre
Dernière intervention
8 mars 2008

Je vais finir par désespérer ...
Messages postés
8
Date d'inscription
samedi 7 août 2004
Statut
Membre
Dernière intervention
8 mars 2008

Peut etre today ?
Messages postés
35
Date d'inscription
mardi 7 novembre 2006
Statut
Membre
Dernière intervention
18 septembre 2009

Peut-être un peu tard, parce que la discussion date d'un an, mais, à tout hasard: cet algorithme fonctionne parce qu'il s'agit d'une fonction récursive (qui se mord la queue, qui s'appelle elle-même). La fonction s'appelle "permutation", et à l'intérieur d'elle-même, elle fait appel à "permutation()".

Pour comprendre la notion de récursivité, se poser la question:
Que sont mes ancêtres ?
Réponse: mon père, et ses ancêtres !

Homme de Néanderthal