Como funciona o embaralhamento Fisher-Yates, sem matemática pesada

Embaralhar uma lista parece simples, mas há maneiras erradas de fazer isso. A mais comum é ordenar a lista por números aleatórios, o que, dependendo da implementação, favorece certas ordens. O método correto tem nome: Fisher-Yates.

A ideia é percorrer a lista do fim para o começo. Em cada posição, sorteia-se um índice entre o início da lista e essa posição, inclusive, e troca-se o item atual pelo item sorteado. Quando o percurso termina, a lista está embaralhada e todas as ordens possíveis têm exatamente a mesma chance.

O detalhe delicado está em sortear o índice. Se você pega um número aleatório muito grande e usa o resto da divisão pelo tamanho desejado, os primeiros valores aparecem um pouco mais do que os outros, quando o tamanho não divide o espaço de números. A solução é a rejeição: descartar os valores que sobram e sortear de novo. Assim, cada índice tem a mesma chance.

Com a semente pública, o embaralhamento é determinístico. Os mesmos dados sempre geram a mesma ordem, e é isso que permite a verificação. O primeiro vencedor é o primeiro item da lista embaralhada, o segundo é o próximo, e assim por diante.

No sorteio de times, a mesma lista embaralhada é dividida em rodízio.

A página do algoritmo mostra o código completo para você refazer o cálculo.