Permutation
Résolu/Fermé
manajac
-
10 juil. 2008 à 00:24
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 - 10 juil. 2008 à 17:32
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 - 10 juil. 2008 à 17:32
1 réponse
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
10 juil. 2008 à 01:11
10 juil. 2008 à 01:11
C'est juste un parcours d'arbre, ou chaque noeud de l'arbre stocke les entiers encore disponibles, jusqu'à atteindre une feuille qui ne contient plus qu'un entier. Exemple avec {1,2,3} :
Pas la peine de programmer une structure d'arbre, il suffit de programmer une fonction récursive à faire "comme si" on parcourait cet arbre.Ainsi ta fonction récursive sera du genre :
Bonne chance
\-- 1 2 3 \-- 1 2 \-- 1 (séquence 3 2 1) \-- 2 (séquence 3 1 2) \-- 1 3 \-- 1 (séquence 2 3 1) \-- 3 (séquence 2 1 3) \-- 2 3 \-- 2 (séquence 1 3 2) \-- 3 (séquence 1 2 3)
Pas la peine de programmer une structure d'arbre, il suffit de programmer une fonction récursive à faire "comme si" on parcourait cet arbre.Ainsi ta fonction récursive sera du genre :
// la fonction appelée récursivement par ton programme parcours_rec(liste_entier restants,liste_entier choisis){ si |restants| <= 1 // plus qu'un élément // rq: le cas == 0 survient si on veut afficher les permutations de la liste vide écrire choisis écrire restant sinon pour chaque élément i appartenant à restant restants_rec = restant \ {i} choisis_rec = choisis ^ {i} // ou ^ désigne l'opérateur de concaténation parcours_rec(restants_rec,choisis_rec) fin pour fin si } // la fonction que tu appelles dans ton programme parcours(liste_entier liste){ parcours_rec(liste,liste_vide); }
Bonne chance
10 juil. 2008 à 17:32