algorithme de Heap

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 premières permutations sont celles ne modifiant pas les derniers éléments. Il existe donc une unique suite infinie de permutations dont l'algorithme renvoie toujours des préfixes (suite de l'OEIS).