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.

Nº Q16907296 ★

Commune · Savoirs

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.

Sur Wikipédia

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 k ! {\textstyle k!} premières permutations sont celles ne modifiant pas les n − k {\displaystyle 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).

Texte : Wikipédia, CC BY-SA 4.0. · Image : Torsten Mütze (CC BY-SA 4.0) ·

Cartes voisines

Ouvrir

…

Confirmation