Inspiration quotidienne
L'excellence du design, chaque jour.
Œuvres sélectionnées par le jury du A' Design Award, présentées chaque matin.
10 entiers. 3,628,800 arrangements possibles. En voici un.
Un mélange pose une question mathématique précise : étant donné n objets distincts, produire l'un des n! ordres possibles, chacun avec une probabilité identique. Pour 10 entiers, cela représente 3,628,800 permutations. La séquence ci-dessus a été sélectionnée dans cet espace avec une probabilité uniforme, générée entièrement dans votre navigateur à l'aide de l'algorithme de Fisher-Yates et de l'API Web Cryptography.
Ronald Fisher et Frank Yates ont décrit la méthode originale de mélange dans leur ouvrage de 1938, Statistical Tables for Biological, Agricultural and Medical Research. Donald Knuth l'a ensuite affinée pour une implémentation informatique dans The Art of Computer Programming (1969). La version moderne parcourt le tableau à rebours. À chaque position, elle sélectionne un élément aléatoire parmi la portion non encore mélangée et les échange. Un seul passage à travers les données produit un mélange uniforme parfait en temps O(n) avec un espace supplémentaire O(1).
La preuve de correction montre qu'après le traitement de la position k, chacun des k! sous-arrangements possibles des k premiers éléments est équiprobable. Par induction, le résultat final couvre les n! permutations avec une probabilité uniforme. Une erreur d'implémentation courante, le « mélange naïf », sélectionne dans l'ensemble du tableau à chaque étape au lieu de la portion non traitée. Cela produit nn séquences d'échanges projetées sur n! permutations. Comme nn n'est généralement pas divisible par n!, certaines permutations deviennent plus probables que d'autres. L'algorithme de Fisher-Yates évite entièrement ce problème.
La croissance factorielle dépasse toute autre fonction mathématique courante. Dix éléments produisent 3 628 800 arrangements. Vingt éléments en produisent plus de 2,4 trillions. Un jeu standard de 52 cartes génère environ 8,07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7 ordres possibles. Ce nombre dépasse le nombre estimé d'atomes dans l'univers observable.
Imaginez : si chaque atome de l'univers mélangeait un jeu de cartes une fois par nanoseconde, et ce depuis le Big Bang il y a 13,8 milliards d'années, le nombre total de mélanges effectués ne représenterait encore qu'une fraction infime de 52!. Chaque mélange que vous effectuez sur cette page crée presque certainement un arrangement qui n'a jamais existé auparavant et n'existera plus jamais.
Un point fixe est un nombre qui se retrouve à sa position d'origine après le mélange. Observez les cercles à anneau doré ci-dessus : ce sont vos points fixes. Le nombre attendu de points fixes est exactement 1, quel que soit le nombre d'éléments mélangés. Dix éléments, un point fixe attendu. Dix mille éléments, toujours un.
La probabilité qu'un élément spécifique reste fixe est 1/n. Sommée sur n éléments, l'espérance vaut 1. Ce résultat, lié au concept mathématique des dérangements étudié par Leonhard Euler, signifie qu'environ 36,8 % de tous les mélanges n'ont aucun point fixe, 36,8 % en ont exactement un, 18,4 % en ont exactement deux, et les probabilités diminuent rapidement au-delà.
Persi Diaconis et Dave Bayer ont démontré en 1992 qu'un mélange riffle standard d'un jeu de 52 cartes nécessite exactement sept itérations pour atteindre une randomisation adéquate. Un mélange numérique de Fisher-Yates accomplit ce que sept mélanges riffle physiques approximent : une randomisation uniforme parfaite en un seul passage informatique.
Demandez à chaque élève de visiter /sequence/1/10 et de mélanger une fois. Puis demandez : est-ce que deux élèves ont obtenu le même ordre ? Avec 3 628 800 arrangements possibles, une correspondance est extraordinairement improbable. Pour une démonstration au vidéoprojecteur, ouvrez /sequence/1/52 et mélangez plusieurs fois. Les anneaux colorés se dispersent en de nouveaux motifs à chaque fois, rendant le hasard immédiatement visuel. L'outil ne nécessite aucun compte, ne dépose aucun cookie et ne stocke aucune donnée d'élève.
Envoyez ce lien. Ils obtiennent la même plage, leur propre permutation unique.
Inspiration quotidienne
Œuvres sélectionnées par le jury du A' Design Award, présentées chaque matin.
