permutation Résolu

Question

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

mamiemando · Accepted Answer

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

Permutation

1 réponse

Votre réponse

Discussions similaires

Newsletters