Mélange de Fisher-Yates

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.

Exemple de mélange de cinq lettres à l'aide de la version en place de Durstenfeld du mélange Fisher-Yates.

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

Description

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 inclus
       échanger a[j] et a[i]

On peut aussi considérer une version équivalente qui mélange le tableau avec un indice k croissant :

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

Cet algorithme a une complexité linéaire et génère aléatoirement une permutation du tableau. Toutes les permutations sont équiprobables : elles ont la même probabilité d'être générée. Au k-ième pas il y a n - k choix possibles pour la variable j. Il y a donc n! exécutions possibles de l'algorithme. 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

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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fisher–Yates shuffle » (voir la liste des auteurs).

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, Londres, Oliver & Boyd, 1948, 3^e éd. (1^re éd. 1938), p. 26-27
3. Richard Durstenfeld, « Algorithm 235: random permutation », Communications of the ACM, vol. 7, n^o 7,‎ 1964, p. 420
4. Donald E. Knuth, Seminumerical algorithms, vol. 2, Reading, MA, Addison–Wesley, 1969, p. 124-125

Liens externes

• Jeff Atwood, « The Danger of Naïveté », sur Coding Horror (Une comparaison de l'algorithme naïf et de l'algorithme de Fisher-Yates)
• Mike Bostock, « Fisher–Yates Shuffle » (Visualisation de différents mélanges)