Nombres aléatoires en O(1)?

Question

Le problème est: est-ce que j'aimerais pour générer des nombres aléatoires entre 0 et 1000 qui ne se répètent jamais (I. E. 6 ne marche pas deux fois), mais cela ne veut pas recourir à quelque chose comme un O(N) la recherche de valeurs précédentes pour le faire. Est-ce possible?

Answer 1

Initialiser un tableau de 1001 entiers avec les valeurs 0-1000 et de définir une variable, max, pour le courant max de l'indice du tableau (à partir de 1000). Choisir un nombre aléatoire, r, entre 0 et max, remplacez le numéro de la position r avec le nombre à la position max et retourner le nombre maintenant à la position max. Décrémenter max 1 et de continuer. Quand max est de 0, jeu max de retour de la taille du tableau - 1 et recommencer sans avoir besoin de réinitialiser le tableau.

Mise à jour: Bien que j'ai trouvé cette méthode sur mon propre lorsque j'ai répondu à la question, après quelques recherches, je réalise que c'est une version modifiée de Fisher-Yates connu comme Durstenfeld-Fisher-Yates ou de Knuth-Fisher-Yates. Depuis la description peut être un peu de mal à suivre, j'ai fourni un exemple ci-dessous (à l'aide de 11 éléments, au lieu de 1001):

Tableau commence avec 11 éléments initialisés à tableau[n] = n, max commence à 10:

+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
                                ^
                               max    

À chaque itération, un nombre aléatoire r est choisi entre 0 et max, la matrice[r] et tableau[max] sont échangés, le nouveau tableau[max] est retournée, et max est décrémenté:

max = 10, r = 3
           +--------------------+
           v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                       +-----+
                       v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
     +--------------------+
     v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
                 +-----+
                 v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

...

Après 11 itérations, tous les nombres dans le tableau ont été sélectionnés, max == 0, et les éléments du tableau sont mélangées:

+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

À ce stade, max peut être remis à zéro à 10, et le processus peut se poursuivre.

Answer 2

Vous pouvez faire ceci:

1. Créer une liste, 0..1000.
2. Lecture aléatoire de la liste. (Voir shuffle de Fisher-Yates pour une bonne manière de le faire.)
3. Retour nombres dans l'ordre de la mélangées liste.

Donc, cela ne nécessite pas une recherche de valeurs anciennes à chaque fois, mais il nécessite toujours O(N) pour la première shuffle. Mais Nils souligné dans les commentaires, c'est amorti O(1).

Answer 3

Utiliser un Maximum Linear Feedback Shift Register.

C'est faisable en quelques lignes de C et à l'exécution, en fait un peu plus d'un couple de test/branches, un peu plus et le décalage de bits. Ce n'est pas aléatoire, mais il fous la plupart des gens.

Answer 4

Vous pouvez utiliser Un Générateur Linéaire à Congruence. Où m (le module) serait la plus proche de le premier plus grand que 1000. Lorsque vous obtenez un certain nombre de la plage, juste à la suivante. La séquence ne se répète une fois tous les éléments ont eu lieu, et vous n'avez pas à utiliser un tableau. Être conscient des inconvénients de ce générateur de bien (y compris le manque de l'aléatoire).

Answer 5

Vous n'avez même pas besoin d'un tableau pour résoudre celui-ci.

Vous avez besoin d'un masque et d'un compteur.

Initialiser le compteur à zéro et l'incrémenter sur les appels successifs. XOR le compteur avec le masque de bits (choisis aléatoirement au démarrage, ou fixe) pour générer un psuedorandom nombre. Si vous ne pouvez pas avoir les chiffres qui dépassent 1000, ne pas utiliser un masque de bits, large de plus de 9 bits. (En d'autres termes, le masque de bits est un entier qui n'est pas au-dessus de 511.)

Assurez-vous que lorsque le compteur passe à 1000, vous le remettre à zéro. À ce moment, vous pouvez sélectionner un autre masque de bits aléatoires — si vous voulez — pour produire le même ensemble de nombres dans un ordre différent.