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
Bonjour,
je cherche une solution pour faire toutes les permutations possibles d'un tableau composé de n entiers
je travaille sur Pascal mais peu importe dans quel language sera la réponse car ce qui compte pour moi est plutot
l'idée
merci d'avance
kebsi skandre

1 réponse

mamiemando Messages postés 33426 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 13 décembre 2024 7 809
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} :
\-- 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
2
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
10 juil. 2008 à 17:32
bonne idée
0