Comment tirer aléatoirement, l'un après l'autre jusqu'à épuisement, les éléments d'un tableau ? La solution qui vient spontanément à l'esprit n'est pas efficace : elle consiste à générer un indice aléatoire, vérifier si l'élément figurant à cet indice a déjà été tiré, et si tel est le cas, recommencer.
A ce petit jeu, il est probable que le temps pris pour tirer un élément s'allonge tandis que le nombre d'éléments tirés s'accroit.
Ne peut-on procéder plus efficacement ?
La solution
La solution s'appuie sur l'algorithme de Fisher-Yates. L'idée est de trier le tableau dans un ordre aléatoire, puis de tirer un à un ses éléments, en le parcourant séquentiellement depuis le début.
Le code JavaScript
En JavaScript, la solution se traduit par le code suivant :
function randomInt (min, max) {
return (min + Math.floor ((max - min + 1) * Math.random ()));
}
function shuffle (items) {
var i, j;
var item;
if ((!items.length) || (items.length == 1))
return;
for (i = items.length - 1; i != 0; i --) {
j = randomInt (0, i);
item = items[j];
items[j] = items[i];
items[i] = item;
}
}
function run () {
var characters = ["P", "A", "N", "D", "A"];
shuffle (characters);
alert (characters.join (""));
}
L'exemple
Cliquez ici pour accéder à une page de test minimaliste. Vous pourrez visualiser le code et le récupérer pour travailler avec.
La logique
Le tableau suivant rend compte, pour chaque entrée d'un tableau contenant les 5 caractères P-A-N-D-A, de l'évolution de la probabilité qu'a l'entrée de rester à sa place lors d'une itération donnée.
Le tableau se lit ainsi :
- A la 1ère itération, l'algorithme échange l'entrée [5] avec une entrée tirée au hasard parmi les entrées [0] à [5]. Dans ces conditions, l'entrée [5] a 1 chance sur 5 de rester en place, tandis que les autres ont 4 chances sur 5 de rester à leur place.
- A la 2ème itération, l'algorithme échange l'entrée [4] avec une entrée tirée au hasard parmi les entrées [0] à [4]. Dans ces conditions, l'entrée [4] a 1 chance sur 4 de rester en place, tandis que les autres ont 3 chances sur 4 de rester à leur place.
- A la 3ème itération, l'algorithme échange l'entrée [4] avec une entrée tirée au hasard parmi les entrées [0] à [4]. Dans ces conditions, l'entrée [4] a 1 chance sur 4 de rester en place, tandis que les autres ont 3 chances sur 4 de rester à leur place.
- etc.
Au final, quelle est la probabilité pour une entrée donnée de rester à sa place ?
- Pour la 1ère entrée, c'est 1/5.
- Pour la 2ème entrée, c'est 4/5 * 1/4 = 1 /5.
- Pour la 3ème entrée, c'est 4/5 * 3/4 * 1/3 = 1 /5.
- etc.
Ainsi, chaque entrée a la même probabilité de rester à sa place (équiprobabilité) : l'algorithme trie les entrées dans un ordre parfaitement aléatoire.
La fonction
randomInt () de tirage aléatoire d'un entier compris entre deux bornes est expliquée ici.