Algoritmo eficiente para gerar números aleatórios únicos (sem repetição)
Eu quero resolver o seguinte problema. Eu tenho que amostrar entre um conjunto extremamente grande, da ordem de 10 ^ 20 e extrair uma amostra sem repetições de tamanho entre 10% e 20%. Dado o tamanho do conjunto, acredito que um algoritmo como Fisher-Yates não é viável.
Eu estou pensando que algo como árvore de caminho aleatório pode funcionar para fazê-lo em O (n log n) e não pode ser feito mais rapidamente, mas quero perguntar se algo assim já foi implementado.
Obrigado pelo seu tempo!