Si tu arrives à générer une permutation aléatoire (telle que toutes les permutations possibles soient équiprobables) en moins que O(n) en temps ou en mémoire je suis intéressé.
Ce n'est pas possible parceque si j'ai une algo permutant aléatoirement un tableau T de taille n avec complexité meilleure que O(n) alors il y a toujours au moins une valeur non permutée tandis qu'il existe des permutations sans point fixe: l'algo n'est pas équiprobable.
Le mélange de Knuth/Fisher-Yates, que tu viens de me faire découvrir, est très beau parceque la preuve d'équiprobabilité est d'une simplicité merveilleuse.
[^] # Re: Permutation
Posté par Michaël (site web personnel) . En réponse au message Générer un nombre pseudo aléatoire avec garantie d'unicité. Évalué à 3.
Ce n'est pas possible parceque si j'ai une algo permutant aléatoirement un tableau T de taille n avec complexité meilleure que O(n) alors il y a toujours au moins une valeur non permutée tandis qu'il existe des permutations sans point fixe: l'algo n'est pas équiprobable.
Le mélange de Knuth/Fisher-Yates, que tu viens de me faire découvrir, est très beau parceque la preuve d'équiprobabilité est d'une simplicité merveilleuse.