Algorithme permutation

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Algorithme permutation

tagsOf

Salut à tous,

J'essaie de trouver un algorithme claire pour pouvoir écrire de manière facile l'algorithme des permutations dons je rappelle brièvement le principe avec un exemple:

Soit un tableau T={1,2,3} (je prend ici 3 valeurs, j'aurai pu en prendre N)

permutation (T);

123
132
213
231
312
321

Je précise que j'ai déjà trouvé des fonctions en C qui me permettent cela, je ne les comprend pas complètement, en voici un exemple:

Code :

#include <stdio.h>
#include <stdlib.h>
void print(const int *v, const int size)
{
if (v != 0) {
for (int i = 0; i < size; i++) {
printf("%4d", v[i] );
}
printf("\n" );
}
} // print
void permutation(int *Value, int N, int k)
{
static int level = -1;
level = level+1;
Value[k] = level;
if (level == N)
print(Value, N);
else
for (int i = 0; i < N; i++)
if (Value[i] == 0)
permutation(Value, N, i);
level = level-1;
Value[k] = 0;
}
int main()
{
const int N = 4;
int Value[N];
for (int i = 0; i < N; i++) {
Value[i] = 0;
}
permutation(Value, N, 0);
return EXIT_SUCCESS;
}

J'ai trouvé également un algorithme que j'ai essayer d'implementer dont je ne saisis complètement pas la ligne en rouge:

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

Voici mon essai d'implémentation en C:

Code :

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

L'exécution donne le résultat inattendu suivant:

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

Si vous pensez détenir un meilleure algorithme dans le sens plus claire a la compréhension, et plus facile à implémenter, ou tous simplement si vous voyez des erreur dans cet algorithme ou dans mon implémentation, n'hésitez pas à m'en faire part, je vous serez trés reconnaissant !

Merci d'avance pour toutes votre aide ! :jap:

Publicité

tagsOf

Voici une autre définition que je vous fait partager:

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

Pas d'idée ?

jxano

Le 'x' est muet

Bonjour,

Pas besoin de récursion pour faire ce travail...

L'idée est de gérer un tableau contenant les indices des éléments pris dans les listes successives. Le premier indice indique l'élément à prendre parmi N : il varie de 0 à N-1. Le deuxième de 0 à N-2, etc. jusqu'au dernier qui reste toujours nul. C'est comme un nombre à plusieurs chiffres où chaque chiffre compte selon une base variable selon le rang du-dit chiffre. Astuce : faire une boucle descendante pour que l'indice de boucle corresponde avec la "base" de chaque indice dans le tableau, c'est-à-dire le nombre d'éléments qui, s'il est atteint, permet de mettre cet indice à zéro et incrémenter le suivant.

Pour déterminer chaque permutation, il est difficile de prendre une chaîne de caractères et de la découper pour éliminer l'élément pris à chaque fois. Le truc est de décaler les éléments restants à droite de celui qui a été pris d'une position vers la gauche.

Si tu possèdes une calculette programmable, commence par faire des essais dessus pour comprendre le système.

Compris ? Vu la politique de la maison, personne n'écrira ton code à ta place...

Bon courage.

Message édité par jxano le 11-03-2008 à 15:26:57

---------------
Honorez les cons : c'est ainsi qu'ils nous fichent la paix.

jesus_christ

votre nouveau dieu

en C++ il y a std::next_permutation
oui je sais ici c'est du C, je signale juste qu'en C++ c'est déjà dans la STL.

Qd je faisais mes études, mon prof de C tolérait qu'on mette du C++ tant qu'on fournissait l'interface en C correspondante.

exemple :

Code :

extern "C" void permutation( int T[], int size )
{
std::sort( T, T + size );
do
{
print( T, size ); /* je reprends ta fonction */
}
while( std::next_permutation( T, T + size ) );
}

Au cas où ça serait un exercice avec un prof aussi tolérant...

Joel F

Real men use unique_ptr

au pire il zieutes dans le source de next_permutation

FORUM HardWare.fr

Programmation

Algorithme permutation

Sujets relatifs
Aide algorithme Ladder (situation industrielle)	Algorithme Pascal
l'algorithme de huffman	Algorithme pour la FFT
[C++] [résolu] Besoin d'un coup de main pour déboguer mon algo de tri	algorithme:arbre binaire de recherche
[JAVA]Algorithme de calcul de la limite de la somme des entiers	Algorithme par séparation et évaluation
Algorithme de permutation de 2 éléments d'une liste simplement chaînée	Algorithme de permutation
Plus de sujets relatifs à : Algorithme permutation

Page générée en 0.062 secondes