Permutations

En mathématiques, les permutations d'éléments sont la liste de tous les arrangements (et ordonnancement) de ces éléments dans tous les ordres possibles.

La méthode la plus connue est l'algorithme de Heap (méthode utilisée par le calculateur de dCode).

Voici un pseudo code source : function permute(data, n) {
if (n = 1) print data
else {
for (i = 0 .. n-2) {
permute(data, n-1)
if (n % 2) swap(data[0], data[n-1])
else swap(data[i], data[n-1])
permute(data, n-1)
}
}
}

Les permutations peuvent ainsi être représentées sous forme d'un arbre des permutations :

Le dénombrement du nombre total de permutations de $ n $ éléments distincts est donné par la factorielle : $$ n! = n \times (n−1) \times (n−2) \times \cdots \times 2 \times 1 $$

Lorsqu'un ensemble contient des éléments répétés, certaines permutations sont identiques. Le nombre de permutations distinctes est alors donné par la formule : $$ \frac{ n! } { n_1! \times n_2! \times \cdots \times n_i! } $$ avec $ n_i $ le nombre d'occurrence de chaque élément répété.

Autrement dit, le fait d'avoir un élément qui se répète divise le nombre total de permutation par le nombre de permutations possibles pour les éléments répétés.