Cadeau: une « cheat sheet » pour vous aider à dénombrer facilement les permutations d’un ensemble.
Si vous vous demandez à quoi ça sert , quel rapport avec le spin, voir « De l’utilisation des permutations« . Ici, nous nous intéresserons uniquement à l’aspect mathématique, en restant (je l’espère) le plus accessible possible.
Pour commencer, un petit rappel illustré de quelques définitions mathématiques (pas besoin d’aspirine, rassurez-vous).
Si on parle souvent de permutations, on travaille en fait plus souvent avec des arrangements, une permutation étant un cas particulier d’arrangement…
Un ensemble de deux éléments (1 et 2) se note {1;2} (remarquez les accolades)
Pour un ensemble, seuls comptent les éléments, pas leur ordre.
L’ensemble {1;2} et l’ensemble {2;1} sont strictement identiques[1].
Cet ensemble simple donne en tout et pour tout deux permutations : (1;2) et (2;1) (ici, notez les parenthèses)
Ces permutations sont tous les arrangements possible des deux éléments de l’ensemble.
Ici, l’ordre est important, et on ne peut pas répéter un élément. Impossible d’écrire (1;1)
Un arrangement de p éléments sur un ensemble de n éléments (avec p<=n) est une liste dans laquelle les éléments sont deux à deux distincts (càd qu'un élément ne peut pas se répéter).
Un arrangement avec p = n est une permutation.
Dans le cas d'un ensemble un peu plus grand, E={1;2;3} , on peut ainsi obtenir
(1;2) ou (3;1) qui sont deux arrangements de 2 éléments sur l'ensemble E.
On peut également identifier les sous-ensembles à 2 éléments de E :
{1;2} , {1;3} , {2;3} (et c’est tout)
Pour un ensemble de n éléments, il existe très exactement n!/(n-p)! arrangements de p éléments[2].
Dans le cas particulier des permutations (n éléments parmi n), la formule se simplifie en n!.
Quand on « ajoute » un élément à un ensemble, on démultiplie donc énormément le nombre de permutations possibles.
Si on passe de 7 à 8 éléments, on multiplie par 8 le nombre de permutations. de 9 à 10, on le décuple, et ainsi de suite.
C’est le phénomène dit d’explosion combinatoire.
La cheat sheet que je vous propose rappelle brièvement les définitions et donne le nombre d’arrangements de p éléments parmi n jusque n=11, ce qui est bien suffisant dans les cas concrets (11! = près de 40 millions…).
Vous remarquerez que pour un ensemble de n éléments, le nombre d’arrangements à n éléments est toujours égal au nombre d’arrangements à (n-1) éléments… C’est tout à fait normal:
Prenons le cas de E={1;2;3} Si on veut tous les arrangements à 2 éléments, on va :
– choisir le premier élément (3 choix possibles)
– choisir le second élément, différent du premier (ne restent que 2 choix possible)
Soit 3×2 = 6 choix différents, 6 arrangements à 2 éléments parmi 3.
Maintenant, si je veux les permutations de E, je vais choisir 3 éléments au lieu de 2. Ca donne quoi ?
– choisir le premier élément (3 choix possibles)
– choisir le second élément, différent du premier (ne restent que 2 choix possible)
– choisir le dernier élément, différent des deux premiers (ne reste.. qu’un seul élément, il n’y a aucun choix)
Soit encore 3x2x1 = 6 choix différents, toujours 6 arrangements possibles.
Ce phénomène est important dans le cas du spinning de texte comme on le verra dans un article dédié.
Si vous avez des questions, ou relevé des erreurs ou inexactitudes sur cet article, n’hésitez pas à m’en faire part ! Dans les commentaires, merci de rester dans le sujet de l’article (l’aspect mathématique) et de ne pas dériver.
Tweeter !
Partager sur Facebook
Plus sur Google+
Epingler sur Pinterest
[1] On pourrait encore écrire {1;2;1;1}, ça serait toujours le même ensemble {1;2}, remarque très importante quand il s’agit d’implémenter pour des textes des indicateurs de distances issus de la théorie des ensembles, comme le coefficient de Dice ou la distance de Jaccard… Quasiment toutes les implémentations que j’ai rencontré sont totalement fausses (elles donnent des résultats, mais qui n’ont rien à voir avec la théorie mathématique sous-jacente, et n’ont donc aucun sens)
[2] n! se lit factorielle n et se calcule comme suit : n! = n(n-1)…2×1