Composez paresseusement une permutation aléatoire des entiers positifs

Question

Y a-t-il des algorithmes efficaces existants pour calculer paresseusement une permutation aléatoire des entiers positifs dans une plage donnée (par exemple, la gamme offerte par un type entier non signé dans un CPU)?

Ce que je veux dire, c'est le suivant:

Un algorithme qui, étant donné une source d'aléatoire et une plage entière positive (pour la simplicité, il pourrait être limité à commencer à 0 et se terminant à n), peut être invité à produire la valeur suivante de cette plage. Cela peut être répété n fois, et un nombre différent est fourni à chaque fois par l'algorithme.

Si l'appelant devait pousser toutes les valeurs récupérées de l'algorithme dans une file d'attente, l'ordre résultant serait tout aussi aléatoire que si le résultat avait été généré avec le shuffle de Fisher - Yates.

L'implémentation naïve serait de choisir un nombre aléatoire dans la plage, de vérifier si elle a déjà été sélectionnée et de choisir à nouveau si c'est le cas. Cet algorithme démarre suffisamment efficace, mais a une complexité croissante pour les appels ultérieurs - trop cher pour les applications du monde réel. Pour être vraiment utile, il faudrait que ce soit O (1) pour chaque essai, bien qu'un bon temps logarithmique puisse être applicable.

Il doit être paresseux car avec de grandes gammes (comme un entier non signé 64 bits), il faudrait des exaocytets de stockage pour précomputer toute la permutation, et il est peu probable qu'une application du monde réel ait réellement besoin de toute la gamme; Il faut simplement que toute la plage ait été prise en compte dans les valeurs qu'il va réellement utiliser.

Essentiellement, le problème est simplement généreusement généreusement une cartographie entre les entiers dans une gamme et une permutation aléatoire de ces mêmes entiers, bien que pouvoir accéder à la cartographie à des points arbitraires au lieu de simplement séquentiellement n'est qu'un bonus.