Permutations

Les permutations d'éléments sont la liste de tous les arrangements et ordonnancement des éléments dans tous les ordres possibles.

Exemple : Les trois lettres A,B,C peuvent être mélangées (anagrammes) de 6 façons : A,B,C B,A,C C,A,B A,C,B B,C,A C,B,A

Les permutations ne doivent pas être confondues avec les combinaisons (pour lesquelles l'ordre n'a pas d'influence) ou avec les arrangements aussi appelées permutations partielles (permutations d'une partie des éléments).

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

Etape 1 - pour chaque élément, le fixer au début

Etape 2 - répéter l'étape 1 avec le reste

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

Le dénombrement des permutations fait appel à la combinatoire et utilise les factorielles.

Exemple : Pour $ n $ éléments, le nombre de combinaisons est $ n! $ (factorielle de $ n $)

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.

Exemple : Les 5 lettres de DCODE ont $ 5! = 120 $ permutations mais comprennent la lettre D en double (ces $ 2 $ lettres D ont $ 2! $ permutations), diviser le nombre total de permutations $ 5! $ par $ 2! $ soit $ 5!/2!=60 $ permutations distinctes.

Les calculs de permutations engendrent un nombre important de valeurs qui nécessitent de plus gros serveurs de calcul avec de plus grandes mémoires, d'où le fait que les générations ne sont pas gratuites.