Microsoft Tropeça no Embaralhamento Aleatório

Semana passada a Microsoft disponibilizou uma página para seleção do browser a instalar no Windows, conforme ela tinha se comprometido a fazer sete meses atrás (a culpa pela demora foram as complicadas negociações). Como parte do acordo, os cinco browsers devem vir em ordem aleatória na página.

Entretanto, algumas pessoas repararam que as posições não eram tão aleatórias assim. Teorias de conspiração pipocaram pela internet, mas o que interessa é uma análise séria e completa. O artigo linkado merece ser lido do começo ao fim, vou falar aqui apenas alguns pontos.

O primeiro é que os testes comprovaram que realmente as posições não eram aleatórias. Mais curioso, as probabilidades mudavam conforme o browser usado para ver a página.

Analisando o código Javascript de embaralhamento, Rob Weir descobriu o "algorítimo" utilizado pelo desenvolvedor (estagiário?) da Microsoft. Resumidamente, ele mandou ordenar a lista com uma função personalizada de comparação, que retornava um valor aleatório, independente do que estava sendo comparado. O que ele parece não ter se tocado é que um algorítimo de ordenação pode comparar mais de uma vez os mesmos elementos e parte do pressuposto que existe uma ordem fixa entre os itens. No momento que ele quebrou este pressuposto, todas as apostas ficam inválidas (como dizem os norte americanos).

Como fazer um embaralhamento correto? Existem três técnicas básicas:

• Montar uma lista com todas as combinações possíveis (no caso 120) e escolher aleatóriamente uma delas.
• Associar a cada item um número aleatório e usar este número como chave para a ordenação.
• Embaralhar trocando aleatoriamente itens da lista.

A terceira opção é a melhor, e uma forma consagrada é o "Fisher-Yates shuffle". Descrevendo este algorítimo de forma informal:

• O embaralhamento é feito in-place, trocando de lugar pares de itens.
  
• Durante a execução do algorítimo, os itens já embaralhados estão no final da lista e os a embaralhar no início. No início toda a lista esta por embaralhar; no final toda a lista foi embaralhada.
• Em cada passo do algorítimo, escolhe-se aleatoriamente um item da parte não embaralhada e troca-se este item com o último da parte não embaralhada. Em seguida diminui-se de uma posição a parte não embaralhada (e consequentemente aumenta-se de uma posição a parte embaralhada).

Uma descrição formal pode ser vista no artigo da Wikipedia linkado acima. Uma das vantagens deste algorítimo é que ele requer exatamente N passos para embaralhar uma lista de N itens.