Baralhar é mais difícil do que parece: um milhão de execuções do baralhamento de uma linha

Um milhão de baralhamentos de quatro elementos

Quatro elementos têm vinte e quatro ordens. É pequeno o suficiente para contar exaustivamente, e é isso que faz dele o caso de teste certo: corra um baralhamento um milhão de vezes, conte com que frequência sai cada uma das vinte e quatro, e um baralhamento justo tem de pôr cerca de 41 667 em cada casa. Tudo o que favoreça sistematicamente algumas ordens aparecerá como um alto, e um único número — o qui-quadrado — resume a tabela inteira num veredito. Com 23 graus de liberdade, um método justo pontua à volta de 23, e qualquer coisa acima de 27,32 aconteceria menos de 5 % das vezes só por acaso.

O de uma linha pontuou 125 397. Nem 30, nem 300 — cinco mil vezes o limiar. A ordem mais frequente, BADC, saiu 62 810 vezes; a mais rara, DBCA, 30 998. A ordem original ABCD sobreviveu intacta 62 485 vezes, vez e meia mais do que devia. Passar o mesmo milhão por um Fisher-Yates bem escrito produziu 10,3, que é o aspeto de um método justo: os extremos foram 41 434 e 41 879, uma dispersão de cerca de 1 %. Esticar o teste para cinco elementos alarga ainda mais a distância — 229 683 contra 89,0 — porque cada elemento extra dá ao algoritmo de ordenação mais uma decisão para tomar mal.

Não vinte e quatro probabilidades, mas duas

As contagens não estão dispersas. Ordenadas, caem em dois grupos apertados: oito ordens à volta de 62 500 e dezasseis à volta de 31 250. São exatamente 1/16 e 1/32 de um milhão, e a aritmética fecha — 8 × (1/16) + 16 × (1/32) = 1. Mais quatro milhões de execuções testaram essa hipótese diretamente e produziram um qui-quadrado de 19,7 com 23 graus de liberdade, um bom ajuste. Portanto o baralhamento de uma linha neste motor não é aproximadamente uniforme com um tremor: é uma distribuição de dois valores em que metade da massa de probabilidade está entalada num terço dos resultados.

As oito ordens favorecidas partilham uma propriedade que vale a pena notar: ABCD, ABDC, ADBC, BACD, BADC, BDAC, DABC e DBAC mantêm todas o C fora das duas primeiras posições. Não é misticismo, é o algoritmo de ordenação a transparecer. Um array de quatro elementos é curto, por isso o V8 nunca sai do seu caminho de inserção binária; o comparador é chamado 4,5 vezes em média, e 4,5 lançamentos de moeda não podem gerar 24 resultados equiprováveis, porque 24 não divide nenhuma potência de dois. O enviesamento está cozido na forma da árvore de decisão antes sequer de o acaso entrar.

O enviesamento pertence ao motor, não à linguagem

A ECMA-262 exige que a função de comparação passada a sort seja um comparador coerente: transitivo, antissimétrico e que dê a mesma resposta para o mesmo par sempre. Um comparador construído sobre Math.random parte os três numa só chamada. A resposta da especificação não é definir o que acontece, mas dizer que se o comparador for incoerente o resultado da ordenação fica definido pela implementação. Essa única frase é a história toda. Não escreveu um baralhamento com estatísticas invulgares — escreveu um programa cuja saída a norma se recusa a especificar.

A consequência prática é que estas contagens medem um motor numa versão, não uma constante universal. O V8 mudou a sua ordenação mais de uma vez; uma execução noutro motor, ou no mesmo após uma atualização, produzirá outra distribuição irregular, e um array suficientemente longo para disparar o caminho de fusão produzirá ainda outra. Nada na norma o proíbe, e nada o avisa quando acontece. Um baralhamento cujas propriedades estatísticas se mexem quando se aplica um patch ao ambiente de execução não é um baralhamento testável.

Fisher-Yates e o erro de índice que o arruína

O algoritmo correto — o Algoritmo P de Knuth — percorre o array do último índice até ao segundo, e em cada posição i tira um índice j uniformemente entre 0 e i inclusive, trocando depois as posições i e j. Três detalhes sustentam toda a demonstração. O ciclo desce. O sorteio inclui o próprio i, portanto um elemento pode ficar onde está. E o intervalo encolhe em um a cada iteração, de modo que o número de caminhos de execução é n × (n−1) × … × 2 = n!, exatamente o número de permutações. Uma bijeção entre caminhos de execução e resultados é o que significa uniformidade, e vale para todo n, não apenas para os que testou.

Mude um carácter e parte-se. A variante comum percorre o array para cima e tira j do array inteiro de cada vez, o que parece mais aleatório e não é. Essa versão tem n^n caminhos de execução, e n^n nunca é múltiplo de n! para n acima de 2, pelo que algumas permutações têm de ser alcançáveis por mais vias do que outras. Medida no mesmo milhão de execuções pontuou 29 913 — mil vezes o limiar, com a ordem mais frequente em 58 698 e a mais rara em 31 233. É o mais perigoso dos dois erros precisamente porque se parece com a versão do manual e passa em qualquer inspeção a olho.

Enviesamento do módulo: a segunda forma de torcer um baralhamento

Fisher-Yates precisa de um inteiro uniforme num intervalo, e a forma óbvia de o obter de um valor aleatório de 32 bits é tirar o módulo do tamanho do intervalo. Isso é uniforme só quando o intervalo divide exatamente 2^32. Normalmente não divide: 2^32 módulo 52 é 48, portanto 48 dos 52 resultados recebem mais uma pré-imagem do que os outros quatro. A 32 bits o excesso resultante anda pelo milionésimo de por cento e ninguém o verá alguma vez. Encolha a fonte para um único byte e a mesma aritmética torna-se brutal: 256 módulo 52 é outra vez 48, mas agora 48 resultados ficam com 5 pré-imagens e 4 com apenas 4 — um excesso de 25 %, visível em uns poucos milhares de sorteios.

A correção é a amostragem por rejeição e não custa quase nada. Calcule o maior múltiplo do intervalo que cabe na sua fonte — para um sorteio de 32 bits e um intervalo de 52 é 2^32 menos 48 — sorteie de novo sempre que o valor caia acima disso, e tire o módulo apenas dos valores aceites. A região de rejeição são 48 valores em 4 294 967 296, portanto o número esperado de sorteios extra é de cerca de um em noventa milhões. Paga uma comparação por chamada e compra uniformidade exata, a melhor troca deste artigo inteiro.

Math.random não é uma máquina de baralhar

Mesmo um Fisher-Yates perfeito está limitado pelo gerador que tem por baixo. Um baralho de 52 cartas tem 52! ordens, ou seja 8,07 × 10^67, cerca de 2^225,6. O gerador por trás do Math.random no V8 carrega 128 bits de estado interno, logo pode alcançar no máximo 2^128 ≈ 3,4 × 10^38 ordens de baralho — uma fração de 4,2 × 10^-30 do total. A esmagadora maioria dos baralhamentos de um baralho padrão simplesmente não é produzível, por muitas vezes que o chame. É um teto matemático duro, não uma falha de implementação, e aplica-se a todo o gerador pseudoaleatório com menos estado do que o espaço que lhe é pedido cobrir.

Outras duas propriedades contam na prática. O Math.random não é semeável nem reproduzível: a especificação não oferece forma de fixar um ponto de partida, e exige explicitamente que realms distintos produzam sequências distintas, pelo que um bug que viu uma vez não pode ser repetido. E não é imprevisível no sentido criptográfico — um observador que veja saídas suficientes pode reconstruir o estado e prever o resto. Se alguém puder ganhar ao adivinhar o seu baralhamento — uma rifa, um sorteio com prémio, um token de segurança, tudo o que seja baralhado perante uma plateia — use crypto.getRandomValues, com amostragem por rejeição por cima. Se o baralhamento for um plano de lugares ou um questionário de treino, Math.random com um Fisher-Yates correto serve perfeitamente.

Perguntas frequentes

Ordenar com um comparador aleatório está sempre enviesado, ou só nalguns navegadores?

Sempre enviesado, mas enviesado de forma diferente em cada lado. A norma exige um comparador coerente e declara o resultado definido pela implementação quando não o recebe, pelo que cada motor — e cada versão de cada motor — produz a sua própria distribuição irregular. No Node 26.3.0 o caso de quatro elementos colapsa em apenas duas probabilidades, 1/16 para oito ordens e 1/32 para as outras dezasseis, o que um teste de quatro milhões de execuções confirma com um qui-quadrado de 19,7 com 23 graus de liberdade. Outro motor não lhe dará esses números exatos: dar-lhe-á outros números errados. Isso é pior do que um enviesamento conhecido e fixo, porque não há nada estável contra que testar e uma atualização do ambiente de execução pode mudar a estatística do seu sorteio sem mudar uma linha do seu código.

Como escrevo Fisher-Yates para que fique realmente correto?

Comece no último índice e desça até ao índice 1. Em cada posição i, tire j uniformemente entre 0 e i inclusive, e depois troque os elementos em i e j. Três coisas têm de estar certas ao mesmo tempo: o ciclo desce, o sorteio inclui o próprio i, e o intervalo encolhe em um a cada iteração. Consiga as três e o número de caminhos de execução é exatamente n fatorial, um por permutação, o que torna a saída uniforme para qualquer comprimento de array e não apenas para os que calhou testar. A variante que sobe e tira j de todo o array de cada vez é o erro clássico: tem n elevado a n caminhos, que nunca é múltiplo de n fatorial acima de n = 2, e mediu um qui-quadrado de 29 913 no teste de quatro elementos onde um baralhamento justo pontua à volta de 23.

Preciso de crypto.getRandomValues, ou o Math.random chega?

O teste é se alguém poderia ganhar ao prever o resultado. Baralhar perguntas de um questionário, sentar uma turma, aleatorizar a ordem de exercícios: Math.random dentro de um Fisher-Yates correto serve, e a diferença nunca se verá. Sortear um prémio, escolher uma amostra de auditoria, gerar qualquer coisa que se comporte como um token: use crypto.getRandomValues, porque o Math.random é um gerador pseudoaleatório cujo estado interno se reconstrói a partir de uma série modesta de saídas, após o que todo o valor futuro é previsível. Há uma segunda razão, mais silenciosa. Um baralho de 52 cartas tem cerca de 2^225,6 ordens e o gerador do V8 carrega 128 bits de estado, portanto alcança no máximo uma ordem de baralho em 10^30. Esse teto é inerente ao tamanho do estado, não à qualidade do algoritmo.

O que é exatamente o enviesamento do módulo, e quando importa?

É o que acontece quando se aperta um intervalo que não divide a sua fonte. Pegue num valor aleatório de 32 bits e reduza-o módulo 52: obtém um número de 0 a 51, mas 2^32 dividido por 52 deixa resto 48, portanto 48 desses resultados têm mais um valor de origem a mapear neles do que os quatro restantes. A 32 bits o excesso resultante anda pelo milionésimo de por cento — verdadeiramente desprezável. A mesma aritmética numa fonte de 8 bits é outro animal: 256 módulo 52 também é 48, mas agora os resultados favorecidos recebem 5 valores de origem e os outros apenas 4, um excesso de 25 % que uns poucos milhares de sorteios expõem. A correção é a amostragem por rejeição: rejeitar todo o sorteio igual ou superior ao maior múltiplo do intervalo que caiba na sua fonte, o que para 32 bits e um intervalo de 52 descarta 48 valores em 4,29 mil milhões, cerca de um sorteio em noventa milhões.

Como testo o meu próprio baralhamento sem formação em estatística?

Encolha o problema até poder contar tudo. Pegue num array de quatro elementos, baralhe-o um milhão de vezes e mantenha a contagem de quantas vezes sai cada uma das vinte e quatro ordens — um dicionário indexado pela cadeia concatenada chega. Depois olhe para dois números: a contagem maior dividida pela menor, e a contagem da ordem original por baralhar. Um baralhamento justo dá uma razão perto de 1,01 nesse tamanho de amostra e deixa a ordem original à volta de 1 em 24. Nas medições aqui, o Fisher-Yates deu 1,011 e a ordenação de uma linha deu 2,026, com a ordem intacta a aparecer 50 % mais do que devia. Não precisa do qui-quadrado para ver essa diferença; o qui-quadrado só lhe diz quão impossível é, e 125 397 contra um limiar de 27,32 é quase o mais impossível que uma medição consegue ser.