Retourner entier aléatoire de l'intervalle basé sur le dernier résultat et une graine

Question

Supposons que nous ayons un intervalle d'entiers [A, B].J'aimerais avoir une fonction qui renvoie des membres aléatoires de l'intervalle, sans répétition.Une fois que tous les membres de l'intervalle sont explorés, la fonction commencerait à renvoyer à nouveau la même première séquence aléatoire, dans le même ordre.

Exemple: A= 1, B= 5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

Ceci serait facile à réaliser en mélangeant une matrice de tous les éléments entre A et B et le répéter une fois que la matrice est terminée.Cependant, cela prendrait trop d'espace mémoire, et cela ne convient pas à mon cas (je pourrais avoir des millions d'éléments).

Au lieu de cela, la fonction que j'aimerais avoir plus ou moins comme celle-ci:

f(a, b, n, seed) -> n+1

Où:

a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

L'astuce consiste à connaître un moyen d'obtenir un numéro non répété de l'intervalle basé uniquement sur l'élément renvoyé avant et la graine.En fin de compte, il se comporterait comme une liste circulaire randomisée à son initialisation, mais sans utiliser de l'espace mémoire.

Answer 1

Je vous suggère de choisir une permutation aléatoire sur la plage $ [A, B] $ , c'est-à-dire une fonction bijective $ \ pi: [a, b] \ to [a, b] $ . Ensuite, maintenez un compteur $ i $ qui commence à i= a $ ; à chaque étape, sortie $ \ pi (i) $ puis incrément $ i $ que $ B + 1 $ devient $ a $ ).

Il existe des méthodes standard pour générer une telle permutation aléatoire dans la littérature de cryptographie: rechercher le cryptage de préservation de format. La graine est la clé cryptographique. Vous serez capable de calculer $ \ pi (i) $ in $ o (1) $ temps et $ O (1) $ espace, il faut donc être très efficace et éviter le besoin de beaucoup de stockage.

Si vous insistez que la sortie suivante doit être une fonction de la sortie précédente, vous pouvez laisser $ g (i)= i + 1 $ (sauf que < span class="math-conteneur"> $ g (b)= a $ ), puis laissez $ f (i)=pi ^ {- 1} (g (\ pi (i)) $ , où $ \ pi $ est une permutation aléatoire choisie comme ci-dessus. Cela vous donnera ensuite un cycle aléatoire qui compte à travers les éléments de $ [A, B] $ dans un ordre aléatoire. Les sorties sont la séquence $ f (a) , F (F (a)), F (F (F (F (F (F (F (a))), \ DOTS $ .