Tri aléatoire des éléments d’un tableau

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.
Evolution des probabilités au fil des itérations
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.
Tri aléatoire des éléments d’un tableau