Ispirazione Quotidiana
Eccellenza nel design, ogni giorno.
Opere selezionate dalla giuria dell’A' Design Award, presentate fresche ogni mattina.
12 numeri interi. 479,001,600 disposizioni possibili. Eccone una.
Un mescolamento pone una precisa domanda matematica: dati n oggetti distinti, produrre uno degli n! ordinamenti possibili, ciascuno con identica probabilità. Per 12 numeri interi, ciò significa 479,001,600 permutazioni. La sequenza qui sopra è stata selezionata da quello spazio con probabilità uniforme, generata interamente nel tuo browser utilizzando l'algoritmo di Fisher-Yates e la Web Cryptography API.
Ronald Fisher e Frank Yates descrissero il metodo originale di mescolamento nel loro libro del 1938 Statistical Tables for Biological, Agricultural and Medical Research. Donald Knuth lo perfezionò successivamente per l'implementazione informatica in The Art of Computer Programming (1969). La versione moderna percorre l'array all'indietro. Ad ogni posizione, seleziona un elemento casuale dalla porzione ancora non mescolata e li scambia. Un singolo passaggio sui dati produce un mescolamento uniforme perfetto in tempo O(n) utilizzando O(1) di spazio aggiuntivo.
La dimostrazione di correttezza mostra che dopo aver elaborato la posizione k, ciascuna delle k! possibili sotto-disposizioni dei primi k elementi è ugualmente probabile. Per induzione, il risultato finale copre tutte le n! permutazioni con probabilità uniforme. Un errore comune di implementazione, il "mescolamento ingenuo", seleziona dall'intero array ad ogni passo invece che dalla porzione non ancora elaborata. Questo produce nn sequenze di scambio distribuite su n! permutazioni. Poiché nn generalmente non è divisibile per n!, alcune permutazioni diventano più probabili di altre. L'algoritmo di Fisher-Yates evita completamente questo problema.
La crescita fattoriale supera ogni altra funzione matematica comune. Dieci elementi producono 3.628.800 disposizioni. Venti elementi ne producono oltre 2,4 quintilioni. Un mazzo standard di 52 carte genera circa 8,07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7 ordinamenti possibili. Quel numero supera il conteggio stimato di atomi nell'universo osservabile.
Considerate: se ogni atomo nell'universo mescolasse un mazzo una volta al nanosecondo, e lo facesse dal Big Bang 13,8 miliardi di anni fa, il totale delle mescolate effettuate sarebbe comunque una frazione infinitesimale di 52!. Ogni mescolata che esegui su questa pagina crea quasi certamente una disposizione che non è mai esistita prima e non esisterà mai più.
Un punto fisso è un numero che finisce nella sua posizione originale dopo il mescolamento. Osserva i cerchi con l'anello dorato qui sopra: quelli sono i tuoi punti fissi. Il numero atteso di punti fissi è esattamente 1, indipendentemente da quanti elementi vengono mescolati. Dieci elementi, un punto fisso atteso. Diecimila elementi, sempre uno.
La probabilità che uno specifico elemento rimanga fisso è 1/n. Sommata su n elementi, il conteggio atteso è uguale a 1. Questo risultato, collegato al concetto matematico dei disordinamenti studiato da Leonhard Euler, significa che circa il 36,8% di tutte le mescolate ha zero punti fissi, il 36,8% ne ha esattamente uno, il 18,4% ne ha esattamente due, e le probabilità calano rapidamente oltre.
Persi Diaconis e Dave Bayer dimostrarono nel 1992 che un riffle shuffle standard di un mazzo da 52 carte richiede esattamente sette iterazioni per raggiungere una randomizzazione adeguata. Un mescolamento digitale Fisher-Yates ottiene ciò che sette riffle shuffle fisici approssimano: una randomizzazione uniforme perfetta in un singolo passaggio computazionale.
Fate visitare a ogni studente /sequence/1/10 ed eseguire una mescolata. Poi chiedete: due studenti hanno ottenuto lo stesso ordine? Con 3.628.800 disposizioni possibili, una coincidenza è straordinariamente improbabile. Per una dimostrazione al proiettore, aprite /sequence/1/52 e mescolate ripetutamente. Gli anelli vivaci si disperdono in nuovi pattern ogni volta, rendendo la casualità immediatamente visiva. Lo strumento non richiede account, non imposta cookie e non memorizza dati degli studenti.
Invia questo link. Riceveranno lo stesso intervallo, con la propria permutazione unica.
Ispirazione Quotidiana
Opere selezionate dalla giuria dell’A' Design Award, presentate fresche ogni mattina.
