Existe um algoritmo que produz um embaralhamento eficiente de um uint32 em um uint32 diferente que resulta em um mapeamento 1:1 quando recebe uma semente aleatória alterável?
Minha orientação inicial sobre isso é um algoritmo em que a semente expressa de alguma forma quais bits reorganizar no número (de modo que 0000 0101 se torne 0100 1000 com a semente [0->6, 2->3]), mas não tenho certeza de como gerar uma maneira de fazer esse embaralhamento de forma eficiente.
Algumas restrições:
- A produção do algoritmo para realizar o embaralhamento a partir da semente não precisa ser muito rápida
- Na verdade, executar o shuffle em um uint32 deve ser rápido
- Não deve haver repetições na saída para uma semente fornecida (um uint32 exclusivo produz um uint32 exclusivo)
Se o objetivo principal é mapear todos os inteiros no intervalo [0..N] para inteiros únicos arbitrários dentro do mesmo intervalo, então há uma maneira rápida e bem conhecida de fazer isso: o inverso multiplicativo .
Eric Lippert escreveu um post de blog sobre isso há cerca de 10 anos, demonstrando como funciona. Era parte de sua série "Matemática do Zero". Aqui está o primeiro dos dois artigos sobre o inverso multiplicativo: https://ericlippert.com/2013/11/12/math-from-scratch-part-thirteen-multiplicative-inverses/
O algoritmo tem um custo único para calcular alguns coeficientes, mas então calcular o inverso de qualquer número é uma questão de algumas multiplicações. É rápido.
Eu uso esse algoritmo quando preciso ofuscar chaves sequenciais. Por exemplo, o primeiro usuário a se inscrever obtém o ID de usuário 1. Internamente, isto é. Mas o ID de usuário que ele vê pode ser 1879632. E o próximo ID de usuário é o #2 internamente. Mas o ID de usuário externo que todos veem é 5034832.
A operação é reversível. Dado o id sequencial (ou seja, '1'), você pode gerar o id de usuário exibido (11879632). E, dado o id de usuário exibido, você pode derivar o id sequencial.
Também escrevi uma entrada de blog mostrando como usá-lo.