Embaralhar linhas

Embaralhar é onde quase toda ferramenta erra

Parece a coisa mais simples do mundo, e é o contrário: a versão que se escreve de cabeça está errada, e o erro é invisível. Ela é esta, e ela está viva em três das ferramentas brasileiras que aparecem nesta busca:

lista.sort(() => Math.random() - 0.5)

O problema é que ordenar exige uma resposta consistente: se “a” vem antes de “b”, tem de vir antes toda vez que a pergunta for feita. Aí está um comparador que responde diferente para o mesmo par, e o algoritmo de ordenação faz o que der. Medimos aqui, com 200 mil embaralhamentos de uma lista de 6 itens: o primeiro item volta em primeiro lugar em 29,6% das vezes no Chrome 151, e em 28,4% no Node 24 — contra os 16,7% de um sorteio justo. Quase o dobro nos dois. E uma ordem específica apareceu 22,6 vezes mais do que devia no Chrome, 33 vezes mais no Node: o tamanho da vantagem muda com a versão do motor, a vantagem não.

Numa fila de apresentações, isso é a mesma pessoa começando quase o dobro das vezes. Num sorteio de brinde, é o primeiro nome da planilha ganhando com vantagem que ninguém combinou. Esta ferramenta usa Fisher-Yates, que é o algoritmo em que todas as ordens têm a mesma chance, e sorteia cada posição por rejeição em vez de resto de divisão — porque 2³² não é múltiplo de 5, e um simples % 5 daria uma vantagem permanente às primeiras posições da lista.

O que “aleatório” do navegador não dá conta

As três ferramentas que acertam o algoritmo ainda esbarram numa parede menos conhecida. O Math.random() do Chrome, do Firefox e do Safari é o mesmo gerador desde 2016 — o xorshift128+, que o próprio time do V8 documentou —, e ele tem 128 bits de estado. Isso significa 2¹²⁸ ≈ 3,4 × 10³⁸ sequências possíveis. Uma lista de 35 linhas tem 35! ≈ 1,0 × 10⁴⁰ ordens.

A conta não fecha: a partir de 35 linhas, a maioria das ordens possíveis não pode sair, por mais que você aperte o botão. Não é opinião, é aritmética — o gerador não tem estados suficientes para representá-las. Aqui o sorteio usa crypto.getRandomValues, o gerador criptográfico que o sistema operacional realimenta, e que não tem esse teto.

Sorteio com semente: como provar depois que foi limpo

Este é o modo que nenhuma ferramenta brasileira desta busca oferece, e ele resolve um problema real: você sorteia a ordem de dez candidatos, publica o resultado, e alguém pergunta como sabe que você não apertou o botão até sair o que queria. Com o sorteio justo, não tem resposta — ninguém consegue refazer um sorteio que veio de acaso puro, nem nós.

No modo com semente, a ordem é uma função do texto que você escreve. A mesma semente devolve sempre a mesma ordem, em qualquer computador, hoje ou daqui a cinco anos. Você publica a semente junto com o resultado, e quem duvidar refaz.

Escolher bem a semente é metade do serviço. Uma semente que você inventou depois de ver a lista não prova nada — dá para ficar tentando sementes até uma delas dar o resultado que interessa. O que prova é uma semente que ninguém podia prever quando a lista foi publicada: anuncie antes que o sorteio vai usar, digamos, os números do primeiro prêmio da Loteria Federal de uma data futura, e use exatamente isso.

O algoritmo, escrito por extenso

Publicar “usamos uma semente” não serve de nada se ninguém puder refazer a conta fora daqui. Então aqui está ela inteira. As linhas entram na ordem em que você colou, numeradas de 0, e:

1. o fluxo de bytes é SHA-256(semente em UTF-8 ‖ 0x00 ‖ número do bloco em decimal), com os blocos 0, 1, 2… em sequência;
2. cada bloco dá 32 bytes, lidos de 4 em 4 como inteiros de 32 bits big-endian;
3. Fisher-Yates de trás para frente: para i de n−1 até 1, sorteia j entre 0 e i e troca as duas posições;
4. cada sorteio descarta o número lido quando ele cai na sobra de 2³² — é o que mantém todas as posições com a mesma chance.

O byte zero entre a semente e o número do bloco não é enfeite: sem ele, a semente “a1” no bloco 2 e a semente “a” no bloco 12 gerariam a mesma conta. E a semente vai em UTF-8 — copie-a exatamente como foi publicada, acentos inclusive.

Em Python, com a biblioteca padrão e nada mais:

import hashlib

def fluxo(semente):
    k = 0
    while True:
        bloco = hashlib.sha256(
            semente.encode("utf-8") + b"\x00" + str(k).encode("ascii")
        ).digest()
        for i in range(0, 32, 4):
            yield int.from_bytes(bloco[i:i + 4], "big")
        k += 1

def embaralhar(linhas, semente):
    r = list(linhas)
    f = fluxo(semente)
    for i in range(len(r) - 1, 0, -1):
        m = i + 1
        teto = (1 << 32) - ((1 << 32) % m)
        x = next(f)
        while x >= teto:          # rejeita a sobra: é o que tira o viés
            x = next(f)
        j = x % m
        r[i], r[j] = r[j], r[i]
    return r

print(embaralhar(["ana","bruno","carla","diego","elena"], "sorteio-2026"))
# ['elena', 'bruno', 'ana', 'carla', 'diego']

Esse resultado não foi digitado nesta página: ele sai do mesmo código que roda no botão acima, no momento em que a página é construída. E a suíte de testes prende essa ordem contra a implementação em Python escrita a partir do texto que você acabou de ler — se as duas se separarem, o teste cai antes de a página subir.

Um item ficou no mesmo lugar. Deu errado?

Não, e vale saber por quê, porque é o motivo pelo qual muita gente aperta o botão várias vezes “até embaralhar direito” — o que, sem perceber, é escolher o resultado a dedo. Num sorteio justo de itens todos diferentes, o número médio de itens que caem na mesma posição é 1. Não é 1 em cem: é 1, em lista de qualquer tamanho, de dez ou de dez mil linhas. Ver um ou dois parados é o normal; nunca ver nenhum é que seria estranho. E se a sua lista tem linhas repetidas, o contador mostra mais que isso — duas linhas iguais que trocam de lugar entre si não se movem aos olhos de ninguém, e ele conta o que dá para conferir na tela.

Serve para sorteio de prêmio?

Para escolher a ordem de apresentações, distribuir vagas de um plantão, montar uma fila de atendimento ou sortear quem paga o almoço, serve e é para isso que ela existe. Para promoção comercial — aquele sorteio de prêmio a título de propaganda —, a conta é outra e não depende de ferramenta nenhuma: a Lei 5.768/1971 diz, no art. 1º, que a distribuição gratuita de prêmios a título de propaganda “dependerá de prévia autorização”, hoje concedida pela Secretaria de Prêmios e Apostas do Ministério da Fazenda. Nenhum site substitui essa autorização, e quem disser o contrário está vendendo problema.

Cabeçalho de planilha e linha em branco

Marque “manter a primeira linha no lugar” quando você colou uma coluna com título — Nome em cima dos nomes. Ela sai do sorteio inteiro, não é embaralhada e devolvida ao topo depois: são coisas diferentes, e a segunda mudaria a ordem de todo o resto.

Linhas em branco saem por padrão, porque linha vazia não é item de lista e sorteá-la junto espalharia buracos no meio do resultado. Desmarcando a caixa, elas entram no sorteio como qualquer outra linha.

Ela mexe no meu texto?

Só na ordem. Cada linha volta letra por letra, com os espaços que tinha — nada é aparado, corrigido ou juntado pelas suas costas. Se o que você quer é limpar a lista antes, isso é trabalho do conversor de texto; se é tirar repetidas, do removedor de linhas duplicadas; e o caminho de volta, quando você quiser desembaralhar em ordem alfabética, é a ordem alfabética.

Quantas linhas ela aguenta?

Muito mais do que se costuma colar. Medido nesta máquina: dez mil linhas em 1 milésimo de segundo, cem mil em 13, e meio milhão de linhas — 13 MB de texto — em 66 milésimos. Com semente, que calcula um SHA-256 a cada oito sorteios, os mesmos meio milhão levam 160. O seu aparelho pode ser mais lento, mas a conta cresce em linha reta. A lista na tela mostra as primeiras duas mil linhas para não travar o navegador desenhando; o botão copia todas.

O texto sai do meu computador?

Não, e nesta busca a pergunta tem peso: das oito ferramentas cujo código lemos antes de escrever esta, duas embaralham no servidor delas — a lista colada viaja pela rede e chega inteira na máquina de outra pessoa. Conferimos por requisição, não por leitura de página: mandamos cinco linhas e elas voltaram embaralhadas de lá.

Aqui o sorteio inteiro acontece dentro do seu navegador. Não existe servidor recebendo a sua lista, não existe cadastro e nada fica guardado — é por isso que o resultado aparece sem espera, e é o que permite colar aqui a lista de nomes dos seus alunos, clientes ou candidatos.