Mélange de Fisher-Yates

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le mélange de Fisher-Yates, aussi appelé mélange de Knuth, est un algorithme pour générer une permutation aléatoire d'un ensemble fini, c'est-à-dire pour mélanger un ensemble d'objets.

Il porte les noms de Ronald Aylmer Fisher, Frank Yates et Donald Knuth.

Description[modifier | modifier le code]

Pour mélanger un tableau a de n éléments (indicés de 0 à n-1), l'algorithme est le suivant.

 Pour i allant de n − 1 à 1 faire :
       j ← entier aléatoire entre 0 et i
       échanger a[j] et a[i]

Cet algorithme a une complexité linéaire et donne toutes les permutations avec la même probabilité. Au k-ième pas il y a n-k choix possibles, donc il y a n! déroulements possibles, de plus l'élément placé en k au pas k ne sera plus jamais modifié dans les pas suivants, ce qui prouve que toutes les permutations seront générées, et avec égale probabilité. Il peut être vu comme un tri par sélection inversé[1].

Historique[modifier | modifier le code]

L'algorithme apparait la première fois dans un ouvrage de Fisher et Yates[2] en 1938. Il est redécouvert sous une forme plus algorithmique par Richard Durstenfeld en 1964[3], puis popularisé par Donald Knuth sous le nom d'algorithme P[4].

Notes et références[modifier | modifier le code]

  1. Paul E. Black, « Fisher-Yates shuffle », sur Dictionary of Algorithms and Data Structures.
  2. Ronald A. Fisher et Frank Yates, Statistical tables for biological, agricultural and medical research, London, Oliver & Boyd, (1re éd. 1938), p. 26-27
  3. Richard Durstenfeld, « Algorithm 235: random permutation », Communications of the ACM, vol. 7, no 7,‎ , p. 420
  4. Donald E. Knuth, Seminumerical algorithms, vol. 2, Reading, MA, Addison–Wesley, , p. 124-125

Liens externes[modifier | modifier le code]