Comment un programme peut-il énumérer toutes les façons de ranger n objets, et combien de temps cela prend-il ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Pour un exercice de NSI, je devais tester tous les ordres de passage possibles de cinq élèves à un oral. J'ai écrit une fonction récursive qui les générait et j'ai obtenu 120 ordres. En essayant avec 12 élèves, l'ordinateur a mis beaucoup plus longtemps. J'ai voulu relier la structure de mon programme à la formule de la factorielle.

L'enjeu et les notions du programme

Faire coïncider un algorithme récursif et une formule de dénombrement, puis estimer son coût.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Une permutation de $n$n objets est une façon de les ranger dans un ordre. Problématique : comment un programme peut-il toutes les produire sans en oublier ni en répéter, et combien y en a-t-il ?

2. 2. Mathématiques : la récurrence de la factorielle

   3,5 min

   Pour ranger $n$n objets, on choisit celui qui vient en premier ($n$n choix), puis on range les $n-1$n-1 restants. Si $P(n)$P(n) est le nombre de rangements, $P(n)=n\times P(n-1)$P(n)=n× P(n-1) et $P(1)=1$P(1)=1, donc $P(n)=n!$P(n)=n!.

   Ordres de grandeur : $5!=120$5!=120, $10!=3628800$10!=3 628 800, $13!\approx 6,2\times 10^9$13!≈6,2×10⁹, $20!\approx 2,4\times 10^{18}$20!≈2,4×10¹⁸. La factorielle dépasse rapidement toute exponentielle de base fixe.

3. 3. NSI : la fonction récursive

   3,5 min

   La fonction permutations(liste) : si la liste a un seul élément, renvoyer cette seule permutation. Sinon, pour chaque élément $x$x de la liste, calculer les permutations des autres éléments et placer $x$x devant chacune d'elles.

   La structure du programme est exactement la récurrence : la boucle « pour chaque $x$x » fait les $n$n choix, l'appel récursif traite les $n-1$n-1 restants. Chaque permutation est produite une seule fois, car elle est déterminée par son premier élément puis par l'ordre des suivants.

   Coût : à un million de permutations par seconde, 10 objets prennent environ 3,6 s ; 13 objets environ 1,7 heure ; 20 objets environ 77 000 ans. Pour les grands $n$n, on n'énumère plus : on cherche directement la permutation voulue, ou on se contente d'un échantillon tiré au hasard.

4. 4. Conclusion

   1,5 min

   Un programme récursif énumère les permutations en reproduisant la récurrence $P(n)=nP(n-1)$P(n)=nP(n-1) : il y en a $n!$n!. Cette croissance factorielle rend l'énumération impossible au-delà d'une quinzaine d'objets. J'ouvre sur le mélange aléatoire de Fisher-Yates, qui tire une permutation uniforme en $n$n étapes.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Confondre permutations (n!) et combinaisons.
• Oublier le cas de base d'une liste à un élément (ou vide).
• Sous-estimer la croissance de n!.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Algorithmique et Python (Terminale spé maths) →

Autres questions : récursivité et récurrence

• Comment être sûr qu'un programme récursif donne toujours le bon résultat ?
• Pourquoi un programme récursif de quatre lignes met-il des secondes à calculer le 30ᵉ terme de Fibonacci ?
• Pourquoi un programme récursif peut-il « déborder » alors que le même calcul en boucle fonctionne ?
• Comment une figure dessinée par un programme récursif peut-elle avoir une aire nulle et une infinité de triangles ?

Toutes les questions maths-nsi →