Algorithme de permutation

Question

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

momsse · Answer

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("
" );
}

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 );
}

cs_jfrancois · Answer

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

momsse · Answer

J'ai bien compris ce que le programme faisait jfrancois, ce que j'aimerais comprendre c'est le principe de l'algo ...

momsse · Answer

Pas d'idée ?

momsse · Answer

Je vais finir par désespérer ...

momsse · Answer

Peut etre today ?

valneandre · Answer

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

Algorithme de permutation

7 réponses

Votre réponse

Discussions similaires