Algorithme de Heap

Une carte des 24 permutations et des 23 transpositions utilisées dans l'algorithme de Heap en permutant les quatre lettres A (orange), B (bleu), C (cyan) et D (rouge foncé).

Diagramme de toutes les permutations de longueur $n=4$ générées par l'algorithme de Heap, représentées par un code couleur (1 = bleu, 2 = vert, 3 = jaune, 4 = rouge).

L'algorithme de Heap génère l'ensemble des permutations d'un ensemble de n objets. Il a été proposé pour la première fois par B. R. Heap en 1963. Chaque permutation est générée à partir de la précédente en n'échangeant que deux éléments : l'algorithme minimise ainsi le nombre d'échanges effectués. Dans une étude de 1977 sur les algorithmes générateurs de permutation, Robert Sedgewick a conclu qu’il était à cette époque l’algorithme le plus efficace pour générer des permutations par ordinateur.

L'algorithme de Heap renvoie toujours les permutations dans le même ordre et ce, quel que soit le nombre d'objets à permuter : les ${\textstyle k!}$ premières permutations sont celles ne modifiant pas les $n-k$ derniers éléments. Il existe donc une unique suite infinie de permutations dont l'algorithme renvoie toujours des préfixes (suite A280318 de l'OEIS).

Détails de l'algorithme

Heap a mis au point une méthode systématique pour produire exactement une fois chaque permutation d'un ensemble à n éléments, en échangeant à chaque étape deux éléments bien choisis.

L'algorithme de Heap repose sur le paradigme diviser pour régner. À la ${\textstyle k}$-ième étape, il génère les ${\textstyle k!}$ permutations des ${\textstyle k}$ premiers éléments, en s'appelant récursivement sur le sous-ensemble qu'ils constituent. Un premier appel est exécuté sans travail préalable pour calculer les permutations fixant le ${\textstyle k}$-ième élément. Ensuite, on échange deux éléments et on exécute un appel récursif supplémentaire, ce à ${\textstyle k-1}$ reprises. La particularité de l'algorithme repose sur le choix des deux éléments à transposer. Heap a trouvé que ce choix pouvait être fait en fonction de la parité de ${\textstyle k}$ : s'il est pair, on échange successivement le ${\textstyle k}$-ième élément avec chacun des ${\textstyle k-1}$ premiers ; s'il est impair, on l'échange toujours avec le premier élément.

// entrée : un entier k, un tableau A avec k <= taille(A)
// effet : l'algorithme écrit successivement les k! permutations du tableau A affectant les k premiers indices
// en appelant l'algorithme avec k = taille(A), on écrit toutes les permutations de A.

// Ici, le tableau A est indexé de 0 à taille(A)-1.

Heap(k : entier, A : tableau) :
    
    Si k = 1 :
        écrire A
    
    Sinon :
        // On génère les permutations fixant A[k-1]
        Heap(k - 1, A)

        // On génère les permutations échangeant A[k-1] avec les autres termes.
        Pour i = 0 à k-2 :
            Si k est pair :
                échanger A[i] et A[k-1]
            Sinon :
                échanger A[0] et A[k-1]
            Fin Si
            
            Heap(k - 1, A)
        
        Fin Pour
    
    Fin Si

On peut encore écrire l'algorithme sous forme itérative  :

// Pour la version itérative, on simule le processus récursif en mémorisant les indices de boucle dans un tableau compteur.
// compteur[k] représente, dans cette simulation, l'indice courant dans la boucle de Heap(k,A).

Heap_iteratif(n : entier, A : tableau) :
    
    compteur := tableau de n entiers, initialisés à 0

    écrire A
    
    // i indique le niveau de la boucle en cours d'incrémentation
    i := 0;

    Tant que i < n :
        
        Si  compteur[i] < i :
            Si i est pair :
                échanger A[0] et A[i]
            Sinon :
                échanger A[compteur[i]], A[i]
            Fin Si
            écrire A
            
            compteur[i] += 1 // on incrémente l'indice de boucle après avoir effectué une itération
            i := 0 // on retourne au cas de base de la version récursive
        
        Sinon :
            // la boucle de niveau i est terminée, on peut donc réinitialiser l'indice et retourner au niveau supérieur
            compteur[i] := 0
            i += 1
        
        Fin Si
    
    Fin Tant que

Preuve de correction

Idée de la preuve

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.

Lemme

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].

Évolution du tableau A au cours de la boucle dans le cas n = 4

Instant	Effet appliqué	État
Avant la boucle	Tableau d'origine	1,2,3,4
Avant la boucle	Heap(n-1, A) : pas de changement	1,2,3,4
Itération 1	Échange des 1er et n-ième termes	4,2,3,1
Itération 1	Heap(n-1, A) : pas de changement	4,2,3,1
Itération 2	Échange des 2ème et n-ième termes	4,1,3,2
Itération 2	Heap(n-1, A) : pas de changement	4,1,3,2
Itération 3	Échange des 3ème et n-ième termes	4,1,2,3
Itération 3	Heap(n-1, A) : pas de changement	4,1,2,3

• 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.

Évolution du tableau A au cours de la boucle dans le cas n = 5

Instant	Effet de bord	État
Avant la boucle	Tableau d'origine	1,2,3,4,5
Avant la boucle	Heap(n-1, A) : rotation partielle	4,1,2,3,5
Itération 1	Échange des 1er et n-ième termes	5,1,2,3,4
Itération 1	Heap(n-1, A) : rotation partielle	3,5,1,2,4
Itération 2	Échange des 1er et n-ième termes	4,5,1,2,3
Itération 2	Heap(n-1, A) : rotation partielle	2,4,5,1,3
Itération 3	Échange des 1er et n-ième termes	3,4,5,1,2
Itération 3	Heap(n-1, A) : rotation partielle	1,3,4,5,2
Itération 4	Échange des 1er et n-ième termes	2,3,4,5,1
Itération 4	Heap(n-1, A) : rotation partielle	1,2,3,4,5

Corollaire du lemme

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.

Théorème

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.

Efficacité de l'algorithme

Par récurrence, on montre que le nombre d'échanges effectués par l'algorithme de Heap (sous forme itérative comme récursive) est d'exactement ${\textstyle n!}$. En cela, elle réalise le minimum d'échanges possibles pour produire l'ensemble des permutations, en plus d'une complexité temporelle en ${\textstyle O(n!)}$.

Plus exactement, le coût temporel d'une méthode de calcul des permutations est ${\textstyle Cn!+P(n)}$ unités de temps du processeur, où ${\textstyle C}$ est une constante et ${\textstyle P}$ une fonction polynomiale qui dépendent en majeure partie de l'implémentation choisie. Par exemple, avec une implémentation itérative classique de la méthode de Heap, ${\textstyle C}$ est de l'ordre de ${\textstyle 37}$.

Étant donnée la croissance explosive de ${\textstyle n!}$, il est très avantageux de diminuer le facteur ${\textstyle C}$ autant que possible. Il est notamment intéressant, ici, d'étudier des implémentations en assembleur, où il est possible d'optimiser directement le nombre d'instructions exécutées par l'ordinateur. Sedgewick fournit plusieurs exemples d'optimisations de ce type réduisant significativement la valeur de ${\textstyle C}$.

Un exemple notable consiste à traiter les permutations par paquets d'un petit nombre ${\textstyle p>1}$, réalisant ainsi des économies en tests et incréments lors du traitement de la boucle, bien qu'avec un coût spatial supplémentaire en ${\textstyle O(p!)}$. Avec ${\textstyle p=4}$, Sedgewick obtient une valeur ${\textstyle C<6}$. Pour lui, cette implémentation était à l'époque, sur la plupart des ordinateurs, la plus efficace pour calculer les permutations.