Mélanger un tableau en JavaScript
Développement et ergonomie
Par djib le mercredi 9 septembre 2009, 13:45 - Lien permanent
Tout à l'heure je suis (encore) tombé sur un code complexe pour trier un tableau aléatoirement en Javascript. Je ne remettrai pas en question les développeurs qui foncent tête baissée dans un développement d'une vingtaine de lignes, mais franchement, pourquoi faire compliqué : la fonction .sort() appliquée à un tableau en Javascript peut prendre en argument une fonction à utiliser pour réaliser le tri. On se retrouve donc avec :
var tableau = [1,2,3,4]; // votre tableau à mélanger tableau.sort(function() { return 0.5 - Math.random() });
Mise à jour le 3/01/2010 : comme l'a justement fait remarquer un lecteur (tcherniatinsky) dans les commentaires, cette méthode n'est pas parfaitement aléatoire ! Je propose une nouvelle solution dans le commentaire 2.
Éventuellement, vous pouvez aussi faire :
// Ajout d'une fonction 'shuffle' aux tableaux (Array) Array.prototype.shuffle = function() { this.sort(function() { return 0.5 - Math.random() }) }; var tableau = [1,2,3,4]; tableau.shuffle();
Allez, je vais conclure sur l'un de mes posters de motivation préféré (dont je ne connais malheureusement pas l'auteur…) :
Commentaires
Si on fait compliqué, c'est parce que la fonction sort avec pour résultat aléatoirement 1 ou -1 ne mélange pas aléatoirement un tableau
en effet :
elle prend les deux premiers éléments
l'éléments 1 a une chance sur 2 d'être en deuxième position, 1 chance sur 2 de rester à sa place;
Puis on compare les deux suivants
le 1 premier élément à une chance sur 8 d'être en 3° position;
S'il y a trois éléments, c'est contaire aux prédictions du hasard qui lui donnait 1 chance sur 6
par exemple abc sera mélangé de la sorte:
abc et bac avec une chance sur 4
et acb cab bca et cba avec une chance sur 8
plus il y a d'éléments et plus la différence est sensible :
avec 10 élements cette probabilité varierait de 2 puissance -9 (1 sur 512)
à 2 puissance -90 (1 sur 1,24E27)
Effectivement, bien vu tcherniatinsky.
Ton raisonnement n'est toutefois pas juste car :
- il y a plusieurs passes ;
- si on a trois éléments, il faut avoir une chance sur 3 (et non sur 6) que le premier élément se retrouve en troisième position ;
- la différence est loin d'être si colossale, même si elle reste conséquente, puisque pour 10 éléments, par la pratique, sur 100000 tris, je trouve que le premier élément ne change pas de place 18390 fois (18,4%), et arrive en dernier 1553 (1,6%).
Bref, on trouve bien un énorme défaut dans la méthode que je propose qui s'appuie sur
sortetMath.random.On trouve ici un intérêt à l'approche
prototypecar il suffit de quelques lignes pour remédier au problème :Array.prototype.shuffle = function() {for ( var position = this.length; position > 0; position-- ) {
// pickup a random element for each index
var random_index = Math.floor( Math.random() * position );
var temp = this[position-1];
this[position-1] = this[random_index];
this[random_index] = temp;
}
}
Et pour s'en convaincre :
function testShuffleIsRandom() {var results = [0,0,0,0,0,0,0,0,0,0];
for ( var test = 0; test < 100000; test++ ) {
var test_array = [1,2,3,4,5,6,7,8,9,10];
test_array.shuffle();
for ( var i = 0; i < test_array.length; i++ ) {
// Look for number 1 in shuffled array
if ( test_array[i] == 1 ) {
results[i] += 1;
}
}
}
return results;
}
console.log(testShuffleIsRandom());
// -> [10034, 10037, 10030, 9797, 10097, 9951, 9881, 10161, 10068, 9944]
Je viens d'écrire cette fonction :
/*
function array_shuffle(a) {
while ( ++i < len ) { j = Math.floor(Math.random()*len); k = Math.floor(Math.random()*len); l = Math.floor(Math.random()*len);tmp = a[i]; a[i] = a[j]; a[j] = a[k]; a[k] = a[l]; a[l] = tmp; } while ( --i >= 0 ) { j = Math.floor(Math.random()*len); k = Math.floor(Math.random()*len); l = Math.floor(Math.random()*len);tmp = a[i]; a[i] = a[j]; a[j] = a[k]; a[k] = a[l]; a[l] = tmp; }}
Si vous avez un avis...
Tu peux essayer de lui appliquer mon test du commentaire précédent pour voir l'efficacité de l'aléatoire.
Effectivement
Cela m'a l'air pas mal :
(10088, 10083, 9913, 10080, 10022, 10104, 9869, 9945, 10016, 9880)
Et j'ai fait quelques tests sur des tableaux plus grands, en cherchant une autre valeur que le 1 (qui est la première dans le tableau de départ).
Mais il me semble que ces tests ne suffisent pas pour affirmer qu'après le mélange un élément à autant de chance de se trouver dans une case plutôt qu'une autre.
Pourquoi est-ce que ça ne serait pas suffisant comme test ? Une probabilité c'est bien compter un nombre de résultats attendus par rapport à un nombre total de possibilités.