Algorithme de Heap

Dans cette démonstration, on utilise la version récursive de l'algorithme décrite plus haut. Cette implémentation est correcte et renvoie chaque permutations une et une seule fois, bien qu'elle ne soit pas optimale (voir la section ci-dessous), mais donne lieu à un raisonnement plus transparent.

La méthode de Heap repose sur un comportement remarquable par lequel, au cours de la boucle d'exécution, chacun des éléments du tableau est placé en dernière position exactement une fois. Ce résultat est ici présenté comme corollaire d'un lemme décrivant l'effet de bord de la méthode sur le tableau, que l'on démontre par récurrence finie.

Soit A un tableau de taille ${\textstyle n}$. Si ${\textstyle n}$ est impair, ${\textstyle A}$ est inchangé après l'exécution de Heap(n, A). Si ${\textstyle n}$ est pair, alors après l'exécution de Heap(n, A), ${\textstyle A}$ aura subi une permutation circulaire vers la droite, ie l'élément d'indice ${\textstyle i}$ est déplacé en position ${\textstyle i+1}$, et le dernier élément se retrouve en première position.

Le résultat est trivialement vrai pour ${\textstyle n=1}$, car l'algorithme ne modifie pas ${\textstyle A}$.

Supposons le résultat vrai pour un certain ${\textstyle i\geq 1}$. Deux cas sont possibles selon la parité de ${\textstyle i+1}$.

• Si l'entier ${\textstyle n=i+1}$ est pair, alors par hypothèse de récurrence le tableau ${\textstyle A}$ est inchangé par les appels récursifs Heap(n-1, A). Ainsi les seules transformations non triviales subies par ${\textstyle A}$ sont les transpositions effectuées à chaque itération de la boucle. L'état final de ${\textstyle A}$ est donc donné par la permutation ${\textstyle (n,n-1)(n,n-2)\dots (n,2)(n,1)}$ qui est égale à la permutation circulaire ${\textstyle (1,2,\dots ,n-1,n-2)}$ Cette égalité se montre par récurrence, puisque après application des ${\textstyle k}$ premières transpositions, le tableau [1,...,n] est envoyé dans l'état [n,1,...,k-1,k+1,...,n-1,k].

• Si l'entier ${\textstyle n=i+1}$ est impair, alors par hypothèse de récurrence le sous-tableau constitué des ${\textstyle i}$ premiers éléments est permuté circulairement à chaque appel de Heap(n-1, A). Ainsi à chaque itération de la boucle, le tableau subit le cycle ${\textstyle (1,\dots ,n-1)}$ puis la transposition ${\textstyle (1,n)}$, ce qui résulte finalement en une permutation circulaire de tout le tableau : ${\textstyle (1,\dots ,n)}$. Cette permutation circulaire étant répétée ${\textstyle n}$ fois (à chaque itération de boucle), le tableau ${\textstyle A}$ est finalement laissé inchangé par l'exécution de la boucle entière.

Soit ${\textstyle A}$ un tableau de taille ${\textstyle n}$. Alors au cours de l'exécution de Heap(n, A), chaque élément va occuper la dernière position du tableau lors d'exactement un appel récursif Heap(n-1, A).

• Si ${\textstyle n=1}$, le résultat est clair.
• Si ${\textstyle n}$ est pair, on a vu que le tableau ${\textstyle A}$ occupait successivement les états induit par les permutations [1,...,n] puis [n,1,...,k-1,k+1,...,n-1,k] pour ${\textstyle k}$ allant de ${\textstyle 1}$ à ${\textstyle n-1}$, avec exactement un appel récursif exécuté entre chaque changement d'état, puis une fois à la fin : le résultat est donc acquis.
• Si ${\textstyle n}$ est impair plus grand que ${\textstyle 1}$, on a vu que le tableau ${\textstyle A}$ subissait ${\textstyle n}$ permutations circulaires successives, avec exactement un appel récursif exécuté avant chacune ; ainsi chaque élément occupe la dernière position au cours d'exactement un d'entre eux.

La méthode de Heap produit chaque permutation du tableau d'entrée exactement une fois.

Si ${\textstyle A}$ est de taille ${\textstyle 1}$, l'unique permutation possible de ${\textstyle A}$ est ${\textstyle A}$ lui-même, ainsi l'algorithme de Heap renvoie trivialement chaque permutation de ${\textstyle A}$ une et une seule fois.

Supposons que l'algorithme de Heap renvoie l'ensemble des permutations de tout tableau d'une taille ${\textstyle i\geq 1}$, sans répétition. Soit ${\textstyle A}$ un tableau de taille ${\textstyle n=i+1}$ . On s'appuie ici sur l'idée qu'une permutation de ${\textstyle A}$ est donnée exactement par les données de son dernier terme, et d'une permutation des ${\textstyle n-1}$ autres éléments. On sait, par hypothèse de récurrence, qu'à chaque itération de la boucle Pour, l'algorithme produit ${\textstyle (n-1)!}$ permutations distinctes. Par ailleurs, par le corollaire du lemme, entre deux itérations différentes les derniers termes des permutations sont distinctes, donc a fortiori les ${\textstyle n!}$ permutations produites par l'algorithme au cours de la boucle sont distinctes deux-à-deux. Puisqu'il existe précisément ${\textstyle n!}$ permutations de ${\textstyle A}$, il vient par dénombrement que chaque permutation est renvoyée une et une seule fois.