NSI (terminale) · Chapitre 5 · Exercice d'entraînement
Problème — Toutes les permutations
La récursivité · Coût et problèmes classiques · niveau 3 (difficile)
Énoncé
Problème — Toutes les permutations.
Une permutation d'une liste d'éléments distincts est une liste contenant les mêmes éléments dans un ordre quelconque.
- Écrire toutes les permutations de
[1, 2, 3]. Combien une liste de éléments a-t-elle de permutations ? - Écrire une fonction récursive
permutations(t)qui renvoie la liste de toutes les permutations det. On pourra choisir le premier élément de toutes les façons possibles, puis permuter les éléments restants. - Pourquoi ne peut-on pas espérer un algorithme de coût polynomial pour ce problème ?
Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.