Utilisateur:Antoine Galet/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$${\textstyle 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}$${\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.

// Au cours de l'exécution Heap(k,A), on renvoie successivement les k! permutations du tableau A affectant les k premiers indices, qui selon l'implémentation exacte de l'algorithme, peuvent être envoyées en sortie ou stockées progressivement.
// L'algorithme a vocation à être appelé avec k = taille(A), ce qui calcule l'ensemble des permutations de A.

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

Heap(k : entier, A : tableau) :
    
    Si k = 1 :
        renvoyer 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

    renvoyer 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
            renvoyer 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

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 preuve emploie le corollaire d'un lemme démontré par récurrence finie, et consiste elle-même en une récurrence.

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

Initialisation : Le résultat est trivialement vrai pour n=1, car l'algorithme ne modifie pas A.

Hérédité : Supposons le résultat vrai pour un certain i >= 1. Deux cas sont possibles selon la parité de i+1.

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

• Cas 2 : Si l'entier n = i+1 est impair, alors par hypothèse de récurrence le sous-tableau constitué des 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 (1, ..., n-1) puis la transposition (1, n), ce qui résulte finalement en une permutation circulaire de tout le tableau (1, ..., n). Cette permutation circulaire étant répétée n fois (à chaque itération de boucle), le tableau 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 A un tableau de taille 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).

• Cas 1 : Si n=1, le résultat est clair.
• Cas 2 : Si n est pair, on a vu que le tableau A occupait successivement les états induit par les permutations [1,...,n] puis [n,1,...,k-1,k+1,...,n-1,k] pour k allant de 1 à 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.
• Cas 3 : Si n est impair plus grand que 1, on a vu que le tableau A subissait 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.

Il ne reste désormais plus qu'à démontrer la correction de l'algorithme, par récurrence.

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

Hérédité : Supposons que l'algorithme de Heap renvoie l'ensemble des permutations de tout tableau de taille i >= 1, sans répétition. Soit A un tableau de taille n=i+1. On s'appuie ici sur l'idée qu'une permutation de A est donnée exactement par les données de son dernier terme, et d'une permutation des n-1 autres éléments. On sait, par hypothèse de récurrence, qu'à chaque itération de la boucle Pour, l'algorithme produit (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 n! permutations produites par l'algorithme au cours de la boucle sont distinctes deux-à-deux. Puisqu'il existe précisément n! permutations de A, il vient par dénombrement que chaque permutation est renvoyée une et une seule fois, ce qui conclut.

Références

[[Catégorie:Permutation]] [[Catégorie:Algorithmes]]