A Matemática do Embaralhamento Justo

Um embaralhamento apresenta uma questão matemática precisa: dados n objetos distintos, produzir uma das n! ordenações possíveis, cada uma com probabilidade idêntica. Para 10 inteiros, isso significa 3,628,800 permutações. A sequência acima foi selecionada desse espaço com probabilidade uniforme, gerada inteiramente no seu navegador usando o algoritmo Fisher-Yates e a API Web Cryptography.

Fisher-Yates: O Algoritmo Definitivo

Ronald Fisher e Frank Yates descreveram o método original de embaralhamento em seu livro de 1938 Statistical Tables for Biological, Agricultural and Medical Research. Donald Knuth posteriormente o refinou para implementação computacional em The Art of Computer Programming (1969). A versão moderna percorre o array de trás para frente. Em cada posição, seleciona um elemento aleatório da porção ainda não embaralhada e os troca. Uma única passagem pelos dados produz um embaralhamento uniforme perfeito em tempo O(n) usando O(1) de espaço extra.

A prova de correção mostra que, após processar a posição k, cada uma das k! sub-ordenações possíveis dos primeiros k elementos é igualmente provável. Por indução, o resultado final cobre todas as n! permutações com probabilidade uniforme. Um erro comum de implementação, o "embaralhamento ingênuo", seleciona do array inteiro em cada passo em vez da porção não processada. Isso produz nⁿ sequências de troca mapeando para n! permutações. Como nⁿ geralmente não é divisível por n!, algumas permutações se tornam mais prováveis que outras. O algoritmo Fisher-Yates evita isso completamente.

A Escala Impressionante das Permutações

O crescimento fatorial supera qualquer outra função matemática comum. Dez itens produzem 3.628.800 arranjos. Vinte itens produzem mais de 2,4 quintilhões. Um baralho padrão de 52 cartas gera aproximadamente 8,07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7 ordenações possíveis. Esse número excede a contagem estimada de átomos no universo observável.

Considere: se cada átomo no universo embaralhasse um baralho uma vez por nanossegundo, e estivesse fazendo isso desde o Big Bang 13,8 bilhões de anos atrás, o total de embaralhamentos realizados ainda seria uma fração infinitesimalmente pequena de 52!. Cada embaralhamento que você realiza nesta página quase certamente cria um arranjo que nunca existiu antes e nunca existirá novamente.

Pontos Fixos: O Paradoxo dos Desarranjos

Um ponto fixo é um número que termina em sua posição original após o embaralhamento. Observe os círculos com anel dourado acima: esses são seus pontos fixos. O número esperado de pontos fixos é exatamente 1, independentemente de quantos itens você embaralhe. Dez itens, um ponto fixo esperado. Dez mil itens, ainda um.

A probabilidade de que um elemento específico permaneça fixo é 1/n. Somada sobre n elementos, a contagem esperada é igual a 1. Este resultado, conectado ao conceito matemático de desarranjos estudado por Leonhard Euler, significa que aproximadamente 36,8% de todos os embaralhamentos têm zero pontos fixos, 36,8% têm exatamente um, 18,4% têm exatamente dois, e as probabilidades caem rapidamente além disso.

O Teorema dos Sete Embaralhamentos

Persi Diaconis e Dave Bayer provaram em 1992 que um embaralhamento riffle padrão de um baralho de 52 cartas requer exatamente sete iterações para alcançar uma aleatorização adequada. Um embaralhamento digital Fisher-Yates alcança o que sete embaralhamentos riffle físicos aproximam: aleatorização uniforme perfeita em uma única passagem computacional.

Na Sala de Aula

Peça a cada aluno que visite /sequence/1/10 e embaralhe uma vez. Depois pergunte: algum par de alunos produziu a mesma ordem? Com 3.628.800 arranjos possíveis, uma correspondência é extraordinariamente improvável. Para uma demonstração no projetor, abra /sequence/1/52 e embaralhe repetidamente. Os anéis vívidos se dispersam em novos padrões a cada vez, tornando a aleatoriedade imediatamente visual. A ferramenta não requer contas, não define cookies e não armazena dados dos alunos.