Nombres aléatoires uniques (non répétitifs) dans O (1)?

Je voudrais générer des nombres aléatoires uniques entre 0 et 1000 qui ne se répètent jamais (c'est-à-dire que 6 ne s'affiche pas deux fois), mais cela ne recourt pas à quelque chose comme une recherche O (N) des valeurs précédentes pour le faire. Est-ce possible?

Initialisez un tableau de 1001 entiers avec les valeurs 0-1000 et définissez une variable, max, sur l'indice max actuel du tableau (en commençant par 1000). Choisissez un nombre aléatoire, r, entre 0 et max, échangez le nombre à la position r avec le nombre à la position max et renvoyez le nombre maintenant à la position max. Décrémentez max de 1 et continuez. Lorsque max est égal à 0, redéfinissez max sur la taille du tableau - 1 et recommencez sans avoir besoin de réinitialiser le tableau.

Mise à jour: Bien que j'aie proposé cette méthode moi-même lorsque j'ai répondu à la question, après quelques recherches, je me rends compte qu'il s'agit d'une version modifiée de Fisher-Yates connue sous le nom de Durstenfeld-Fisher-Yates ou Knuth-Fisher-Yates. Puisque la description peut être un peu difficile à suivre, j'ai fourni un exemple ci-dessous (en utilisant 11 éléments au lieu de 1001):

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

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

A chaque itération, un nombre aléatoire r est sélectionné entre 0 et max, le tableau [r] et le tableau [max] sont permutés, le nouveau tableau [max] est renvoyé 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 du tableau ont été sélectionnés, max == 0, et les éléments du tableau sont mélangés:

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

À ce stade, max peut être réinitialisé à 10 et le processus peut se poursuivre.

Tu peux le faire:

1. Créez une liste, 0..1000.
2. Mélangez la liste. (Voir la lecture aléatoire de Fisher-Yates pour un bon moyen de le faire.)
3. Renvoie les numéros dans l'ordre de la liste aléatoire.

Cela ne nécessite donc pas une recherche des anciennes valeurs à chaque fois, mais cela nécessite toujours O (N) pour le mélange initial. Mais comme Nils l'a souligné dans ses commentaires, il s'agit d'un amortissement O (1).

Utilisez un registre de décalage de rétroaction linéaire maximal .

Il est implémentable en quelques lignes de C et au moment de l'exécution, il ne fait guère plus que quelques tests / branches, un petit ajout et un changement de bits. Ce n'est pas aléatoire, mais cela trompe la plupart des gens.

Vous pouvez utiliser un générateur congruentiel linéaire . Où m(le module) serait le nombre premier le plus proche supérieur à 1000. Lorsque vous obtenez un nombre hors de la plage, obtenez simplement le suivant. La séquence ne se répétera qu'une fois que tous les éléments se sont produits et vous n'avez pas à utiliser de tableau. Soyez conscient des inconvénients de ce générateur (y compris le manque de caractère aléatoire).

Vous pouvez utiliser le cryptage avec préservation du format pour crypter un compteur. Votre compteur va juste de 0 et le cryptage utilise une clé de votre choix pour le transformer en une valeur apparemment aléatoire de la base et de la largeur souhaitées. Par exemple, pour l'exemple de cette question: base 10, largeur 3.

Les chiffrements par blocs ont normalement une taille de bloc fixe de, par exemple, 64 ou 128 bits. Mais le cryptage avec préservation du format vous permet de prendre un chiffrement standard comme AES et de créer un chiffrement de plus petite largeur, de la base et de la largeur que vous souhaitez, avec un algorithme qui est toujours cryptographiquement robuste.

Il est garanti de ne jamais avoir de collisions (car les algorithmes cryptographiques créent un mappage 1: 1). Il est également réversible (un mappage bidirectionnel), vous pouvez donc prendre le nombre résultant et revenir à la valeur de compteur avec laquelle vous avez commencé.

Cette technique n'a pas besoin de mémoire pour stocker un tableau mélangé, etc., ce qui peut être un avantage sur les systèmes avec une mémoire limitée.

AES-FFX est une méthode standard proposée pour y parvenir. J'ai expérimenté du code Python de base basé sur l'idée AES-FFX, bien que pas totalement conforme - voir le code Python ici . Il peut par exemple crypter un compteur sur un nombre décimal à 7 chiffres à la recherche aléatoire ou un nombre de 16 bits. Voici un exemple de base 10, largeur 3 (pour donner un nombre compris entre 0 et 999 inclus) comme la question posée:

000   733
001   374
002   882
003   684
004   593
005   578
006   233
007   811
008   072
009   337
010   119
011   103
012   797
013   257
014   932
015   433
...   ...

Pour obtenir différentes séquences pseudo-aléatoires non répétitives, modifiez la clé de chiffrement. Chaque clé de chiffrement produit une séquence pseudo-aléatoire non répétitive différente.

Pour les nombres faibles comme 0 ... 1000, créer une liste contenant tous les nombres et la mélanger est simple. Mais si l'ensemble de nombres à partir duquel tirer est très grand, il existe un autre moyen élégant: vous pouvez construire une permutation pseudo-aléatoire en utilisant une clé et une fonction de hachage cryptographique. Consultez l'exemple de pseudo-code C ++ suivant:

unsigned randperm(string key, unsigned bits, unsigned index) {
  unsigned half1 =  bits    / 2;
  unsigned half2 = (bits+1) / 2;
  unsigned mask1 = (1 << half1) - 1;
  unsigned mask2 = (1 << half2) - 1;
  for (int round=0; round<5; ++round) {
    unsigned temp = (index >> half1);
    temp = (temp << 4) + round;
    index ^= hash( key + "/" + int2str(temp) ) & mask1;
    index = ((index & mask2) << half1) | ((index >> half2) & mask1);
  }
  return index;
}

Voici hashjuste une fonction pseudo-aléatoire arbitraire qui mappe une chaîne de caractères à un entier non signé éventuellement énorme. La fonction randpermest une permutation de tous les nombres entre 0 ... pow (2, bits) -1 en supposant une clé fixe. Cela découle de la construction car chaque étape qui modifie la variable indexest réversible. Ceci est inspiré d'un chiffrement Feistel .

Vous pouvez utiliser mon algorithme Xincrol décrit ici:

http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html

Il s'agit d'une méthode algorithmique pure de génération de nombres aléatoires mais uniques sans tableaux, listes, permutations ou charge CPU lourde.

La dernière version permet également de définir la plage de nombres, par exemple, si je veux des nombres aléatoires uniques dans la plage de 0-1073741821.

Je l'ai pratiquement utilisé pour

• Lecteur MP3 qui lit chaque chanson au hasard, mais une seule fois par album / répertoire
• Effet de dissolution des images vidéo par pixel (rapide et fluide)
• Création d'un brouillard de "bruit" secret sur l'image pour les signatures et les marqueurs (stéganographie)
• ID d'objet de données pour la sérialisation d'une grande quantité d'objets Java via des bases de données
• Protection des bits de mémoire à triple majorité
• Cryptage adresse + valeur (chaque octet est non seulement crypté mais également déplacé vers un nouvel emplacement crypté dans la mémoire tampon). Cela a vraiment rendu les boursiers de la cryptanalyse en colère contre moi :-)
• Texte brut en clair comme le cryptage de texte crypté pour les SMS, les e-mails, etc.
• Mon calculateur de poker Texas Hold'em (THC)
• Plusieurs de mes jeux pour simulations, "shuffling", classement
• plus

C'est ouvert, gratuit. Essaie...

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

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

Initialisez le compteur à zéro et incrémentez-le lors des appels successifs. XOR le compteur avec le masque de bits (sélectionné au hasard au démarrage, ou fixe) pour générer un nombre pseudo-aléatoire. Si vous ne pouvez pas avoir de nombres supérieurs à 1000, n'utilisez pas de masque de bits plus large que 9 bits. (En d'autres termes, le masque de bits est un entier non supérieur à 511.)

Assurez-vous que lorsque le compteur dépasse 1000, vous le remettez à zéro. À ce stade, vous pouvez sélectionner un autre masque de bits aléatoire - si vous le souhaitez - pour produire le même ensemble de nombres dans un ordre différent.

Je pense que le générateur congruentiel linéaire serait la solution la plus simple.

et il n'y a que trois restrictions à l' un , c et m valeurs

1. m et c sont relativement premiers,
2. a-1 est divisible par tous les facteurs premiers de m
3. a-1 est divisible par 4 si m est divisible par 4

PS, la méthode a déjà été mentionnée mais le message a de fausses hypothèses sur les valeurs constantes. Les constantes ci-dessous devraient fonctionner correctement pour votre cas

Dans votre cas , vous pouvez utiliser a = 1002, c = 757,m = 1001

X = (1002 * X + 757) mod 1001

Voici un code que j'ai tapé qui utilise la logique de la première solution. Je sais que c'est "indépendant du langage", mais je voulais juste présenter cela comme un exemple en C # au cas où quelqu'un chercherait une solution pratique rapide.

// Initialize variables
Random RandomClass = new Random();
int RandArrayNum;
int MaxNumber = 10;
int LastNumInArray;
int PickedNumInArray;
int[] OrderedArray = new int[MaxNumber];      // Ordered Array - set
int[] ShuffledArray = new int[MaxNumber];     // Shuffled Array - not set

// Populate the Ordered Array
for (int i = 0; i < MaxNumber; i++)                  
{
    OrderedArray[i] = i;
    listBox1.Items.Add(OrderedArray[i]);
}

// Execute the Shuffle                
for (int i = MaxNumber - 1; i > 0; i--)
{
    RandArrayNum = RandomClass.Next(i + 1);         // Save random #
    ShuffledArray[i] = OrderedArray[RandArrayNum];  // Populting the array in reverse
    LastNumInArray = OrderedArray[i];               // Save Last Number in Test array
    PickedNumInArray = OrderedArray[RandArrayNum];  // Save Picked Random #
    OrderedArray[i] = PickedNumInArray;             // The number is now moved to the back end
    OrderedArray[RandArrayNum] = LastNumInArray;    // The picked number is moved into position
}

for (int i = 0; i < MaxNumber; i++)                  
{
    listBox2.Items.Add(ShuffledArray[i]);
}

Cette méthode est appropriée lorsque la limite est élevée et que vous ne souhaitez générer que quelques nombres aléatoires.

#!/usr/bin/perl

($top, $n) = @ARGV; # generate $n integer numbers in [0, $top)

$last = -1;
for $i (0 .. $n-1) {
    $range = $top - $n + $i - $last;
    $r = 1 - rand(1.0)**(1 / ($n - $i));
    $last += int($r * $range + 1);
    print "$last ($r)\n";
}

Notez que les nombres sont générés par ordre croissant, mais vous pouvez ensuite les mélanger ensuite.

Vous pouvez utiliser un bon générateur de nombres pseudo-aléatoires avec 10 bits et jeter 1001 à 1023 en laissant 0 à 1000.

De là, nous obtenons la conception d'un PRNG 10 bits.

• 10 bits, polynôme de rétroaction x ^ 10 + x ^ 7 + 1 (période 1023)

• utiliser un LFSR Galois pour obtenir du code rapide

public static int[] randN(int n, int min, int max)
{
    if (max <= min)
        throw new ArgumentException("Max need to be greater than Min");
    if (max - min < n)
        throw new ArgumentException("Range needs to be longer than N");

    var r = new Random();

    HashSet<int> set = new HashSet<int>();

    while (set.Count < n)
    {
        var i = r.Next(max - min) + min;
        if (!set.Contains(i))
            set.Add(i);
    }

    return set.ToArray();
}

N Les nombres aléatoires non répétitifs seront de complexité O (n), selon les besoins.
Remarque: Aléatoire doit être statique avec la sécurité des fils appliquée.

Supposons que vous souhaitiez parcourir les listes mélangées encore et encore, sans avoir le O(n)délai chaque fois que vous recommencez pour les mélanger à nouveau, dans ce cas, nous pouvons le faire:

1. Créer 2 listes A et B, de 0 à 1000, prend de la 2nplace.

2. Mélanger la liste A à l'aide de Fisher-Yates, prend du ntemps.

3. Lorsque vous dessinez un nombre, effectuez un mélange Fisher-Yates en une étape sur l'autre liste.

4. Lorsque le curseur est à la fin de la liste, passez à l'autre liste.

Prétraiter

cursor = 0

selector = A
other    = B

shuffle(A)

Dessiner

temp = selector[cursor]

swap(other[cursor], other[random])

if cursor == N
then swap(selector, other); cursor = 0
else cursor = cursor + 1

return temp

La question Comment générer efficacement une liste de K entiers non répétitifs entre 0 et une borne supérieure N est liée comme un doublon - et si vous voulez quelque chose qui est O (1) par nombre aléatoire généré (sans O (n) coût de démarrage)) il y a une simple modification de la réponse acceptée.

Créez une carte vide non ordonnée (une carte ordonnée vide prendra O (log k) par élément) d'un entier à un entier - au lieu d'utiliser un tableau initialisé. Définissez max à 1000 si c'est le maximum,

1. Choisissez un nombre aléatoire, r, entre 0 et max.
2. Assurez-vous que les éléments de carte r et max existent dans la carte non ordonnée. S'ils n'existent pas, créez-les avec une valeur égale à leur indice.
3. Swap éléments r et max
4. Renvoie l'élément max et décrémente max de 1 (si max devient négatif, vous avez terminé).
5. Revenez à l'étape 1.

La seule différence par rapport à l'utilisation d'un tableau initialisé est que l'initialisation des éléments est reportée / ignorée - mais elle générera exactement les mêmes nombres à partir du même PRNG.

Une autre posibilité:

Vous pouvez utiliser un tableau d'indicateurs. Et prenez le suivant quand il est déjà choisi.

Mais attention après 1000 appels, la fonction ne se terminera jamais donc vous devez faire une sauvegarde.

Voici un exemple de code COBOL avec lequel vous pouvez jouer.
Je peux vous envoyer un fichier RANDGEN.exe afin que vous puissiez jouer avec pour voir s'il veut que vous le vouliez.

   IDENTIFICATION DIVISION.
   PROGRAM-ID.  RANDGEN as "ConsoleApplication2.RANDGEN".
   AUTHOR.  Myron D Denson.
   DATE-COMPILED.
  * ************************************************************** 
  *  SUBROUTINE TO GENERATE RANDOM NUMBERS THAT ARE GREATER THAN
  *    ZERO AND LESS OR EQUAL TO THE RANDOM NUMBERS NEEDED WITH NO
  *    DUPLICATIONS.  (CALL "RANDGEN" USING RANDGEN-AREA.)
  *     
  *  CALLING PROGRAM MUST HAVE A COMPARABLE LINKAGE SECTION
  *    AND SET 3 VARIABLES PRIOR TO THE FIRST CALL IN RANDGEN-AREA     
  *
  *    FORMULA CYCLES THROUGH EVERY NUMBER OF 2X2 ONLY ONCE. 
  *    RANDOM-NUMBERS FROM 1 TO RANDOM-NUMBERS-NEEDED ARE CREATED 
  *    AND PASSED BACK TO YOU.
  *
  *  RULES TO USE RANDGEN:
  *
  *    RANDOM-NUMBERS-NEEDED > ZERO 
  *     
  *    COUNT-OF-ACCESSES MUST = ZERO FIRST TIME CALLED.
  *         
  *    RANDOM-NUMBER = ZERO, WILL BUILD A SEED FOR YOU
  *    WHEN COUNT-OF-ACCESSES IS ALSO = 0 
  *     
  *    RANDOM-NUMBER NOT = ZERO, WILL BE NEXT SEED FOR RANDGEN
  *    (RANDOM-NUMBER MUST BE <= RANDOM-NUMBERS-NEEDED)       
  *     
  *    YOU CAN PASS RANDGEN YOUR OWN RANDOM-NUMBER SEED
  *     THE FIRST TIME YOU USE RANDGEN.
  *     
  *    BY PLACING A NUMBER IN RANDOM-NUMBER FIELD
  *      THAT FOLLOWES THESE SIMPLE RULES:
  *        IF COUNT-OF-ACCESSES = ZERO AND 
  *        RANDOM-NUMBER > ZERO AND 
  *        RANDOM-NUMBER <= RANDOM-NUMBERS-NEEDED
  *       
  *    YOU CAN LET RANDGEN BUILD A SEED FOR YOU
  *     
  *      THAT FOLLOWES THESE SIMPLE RULES:
  *        IF COUNT-OF-ACCESSES = ZERO AND 
  *        RANDOM-NUMBER = ZERO AND 
  *        RANDOM-NUMBER-NEEDED > ZERO  
  *         
  *     TO INSURING A DIFFERENT PATTERN OF RANDOM NUMBERS
  *        A LOW-RANGE AND HIGH-RANGE IS USED TO BUILD
  *        RANDOM NUMBERS.
  *        COMPUTE LOW-RANGE =
  *             ((SECONDS * HOURS * MINUTES * MS) / 3).         
  *        A HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE
  *        AFTER RANDOM-NUMBER-BUILT IS CREATED 
  *        AND IS BETWEEN LOW AND HIGH RANGE
  *        RANDUM-NUMBER = RANDOM-NUMBER-BUILT - LOW-RANGE
  *               
  * **************************************************************         
   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.
   DATA DIVISION.
   FILE SECTION.
   WORKING-STORAGE SECTION.
   01  WORK-AREA.
       05  X2-POWER                     PIC 9      VALUE 2. 
       05  2X2                          PIC 9(12)  VALUE 2 COMP-3.
       05  RANDOM-NUMBER-BUILT          PIC 9(12)  COMP.
       05  FIRST-PART                   PIC 9(12)  COMP.
       05  WORKING-NUMBER               PIC 9(12)  COMP.
       05  LOW-RANGE                    PIC 9(12)  VALUE ZERO.
       05  HIGH-RANGE                   PIC 9(12)  VALUE ZERO.
       05  YOU-PROVIDE-SEED             PIC X      VALUE SPACE.
       05  RUN-AGAIN                    PIC X      VALUE SPACE.
       05  PAUSE-FOR-A-SECOND           PIC X      VALUE SPACE.   
   01  SEED-TIME.
       05  HOURS                        PIC 99.
       05  MINUTES                      PIC 99.
       05  SECONDS                      PIC 99.
       05  MS                           PIC 99. 
  *
  * LINKAGE SECTION.
  *  Not used during testing  
   01  RANDGEN-AREA.
       05  COUNT-OF-ACCESSES            PIC 9(12) VALUE ZERO.
       05  RANDOM-NUMBERS-NEEDED        PIC 9(12) VALUE ZERO.
       05  RANDOM-NUMBER                PIC 9(12) VALUE ZERO.
       05  RANDOM-MSG                   PIC X(60) VALUE SPACE.
  *    
  * PROCEDURE DIVISION USING RANDGEN-AREA.
  * Not used during testing 
  *  
   PROCEDURE DIVISION.
   100-RANDGEN-EDIT-HOUSEKEEPING.
       MOVE SPACE TO RANDOM-MSG. 
       IF RANDOM-NUMBERS-NEEDED = ZERO
         DISPLAY 'RANDOM-NUMBERS-NEEDED ' NO ADVANCING
         ACCEPT RANDOM-NUMBERS-NEEDED.
       IF RANDOM-NUMBERS-NEEDED NOT NUMERIC 
         MOVE 'RANDOM-NUMBERS-NEEDED NOT NUMERIC' TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF RANDOM-NUMBERS-NEEDED = ZERO
         MOVE 'RANDOM-NUMBERS-NEEDED = ZERO' TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF COUNT-OF-ACCESSES NOT NUMERIC
         MOVE 'COUNT-OF-ACCESSES NOT NUMERIC' TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF COUNT-OF-ACCESSES GREATER THAN RANDOM-NUMBERS-NEEDED
         MOVE 'COUNT-OF-ACCESSES > THAT RANDOM-NUMBERS-NEEDED'
           TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF YOU-PROVIDE-SEED = SPACE AND RANDOM-NUMBER = ZERO
         DISPLAY 'DO YOU WANT TO PROVIDE SEED  Y OR N: '
           NO ADVANCING
           ACCEPT YOU-PROVIDE-SEED.  
       IF RANDOM-NUMBER = ZERO AND
          (YOU-PROVIDE-SEED = 'Y' OR 'y')
         DISPLAY 'ENTER SEED ' NO ADVANCING
         ACCEPT RANDOM-NUMBER. 
       IF RANDOM-NUMBER NOT NUMERIC
         MOVE 'RANDOM-NUMBER NOT NUMERIC' TO RANDOM-MSG
         GO TO 900-EXIT-RANDGEN.
   200-RANDGEN-DATA-HOUSEKEEPING.      
       MOVE FUNCTION CURRENT-DATE (9:8) TO SEED-TIME.
       IF COUNT-OF-ACCESSES = ZERO
         COMPUTE LOW-RANGE =
                ((SECONDS * HOURS * MINUTES * MS) / 3).
       COMPUTE RANDOM-NUMBER-BUILT = RANDOM-NUMBER + LOW-RANGE.  
       COMPUTE HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE.
       MOVE X2-POWER TO 2X2.             
   300-SET-2X2-DIVISOR.
       IF 2X2 < (HIGH-RANGE + 1) 
          COMPUTE 2X2 = 2X2 * X2-POWER
           GO TO 300-SET-2X2-DIVISOR.    
  * *********************************************************         
  *  IF FIRST TIME THROUGH AND YOU WANT TO BUILD A SEED.    *
  * ********************************************************* 
       IF COUNT-OF-ACCESSES = ZERO AND RANDOM-NUMBER = ZERO
          COMPUTE RANDOM-NUMBER-BUILT =
                ((SECONDS * HOURS * MINUTES * MS) + HIGH-RANGE).
       IF COUNT-OF-ACCESSES = ZERO        
         DISPLAY 'SEED TIME ' SEED-TIME 
               ' RANDOM-NUMBER-BUILT ' RANDOM-NUMBER-BUILT 
               ' LOW-RANGE  ' LOW-RANGE.          
  * *********************************************     
  *    END OF BUILDING A SEED IF YOU WANTED TO  * 
  * *********************************************               
  * ***************************************************
  * THIS PROCESS IS WHERE THE RANDOM-NUMBER IS BUILT  *  
  * ***************************************************   
   400-RANDGEN-FORMULA.
       COMPUTE FIRST-PART = (5 * RANDOM-NUMBER-BUILT) + 7.
       DIVIDE FIRST-PART BY 2X2 GIVING WORKING-NUMBER 
         REMAINDER RANDOM-NUMBER-BUILT. 
       IF RANDOM-NUMBER-BUILT > LOW-RANGE AND
          RANDOM-NUMBER-BUILT < (HIGH-RANGE + 1)
         GO TO 600-RANDGEN-CLEANUP.
       GO TO 400-RANDGEN-FORMULA.
  * *********************************************     
  *    GOOD RANDOM NUMBER HAS BEEN BUILT        *               
  * *********************************************
   600-RANDGEN-CLEANUP.
       ADD 1 TO COUNT-OF-ACCESSES.
       COMPUTE RANDOM-NUMBER = 
            RANDOM-NUMBER-BUILT - LOW-RANGE. 
  * *******************************************************
  * THE NEXT 3 LINE OF CODE ARE FOR TESTING  ON CONSOLE   *  
  * *******************************************************
       DISPLAY RANDOM-NUMBER.
       IF COUNT-OF-ACCESSES < RANDOM-NUMBERS-NEEDED
        GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.     
   900-EXIT-RANDGEN.
       IF RANDOM-MSG NOT = SPACE
        DISPLAY 'RANDOM-MSG: ' RANDOM-MSG.
        MOVE ZERO TO COUNT-OF-ACCESSES RANDOM-NUMBERS-NEEDED RANDOM-NUMBER. 
        MOVE SPACE TO YOU-PROVIDE-SEED RUN-AGAIN.
       DISPLAY 'RUN AGAIN Y OR N '
         NO ADVANCING.
       ACCEPT RUN-AGAIN.
       IF (RUN-AGAIN = 'Y' OR 'y')
         GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.
       ACCEPT PAUSE-FOR-A-SECOND.
       GOBACK.

La plupart des réponses ici ne garantissent pas qu'elles ne renverront pas le même numéro deux fois. Voici une solution correcte:

int nrrand(void) {
  static int s = 1;
  static int start = -1;
  do {
    s = (s * 1103515245 + 12345) & 1023;
  } while (s >= 1001);
  if (start < 0) start = s;
  else if (s == start) abort();

  return s;
}

Je ne suis pas sûr que la contrainte soit bien spécifiée. On suppose qu'après 1000 autres sorties, une valeur est autorisée à se répéter, mais cela permet naïvement à 0 de suivre immédiatement après 0 tant qu'ils apparaissent tous les deux à la fin et au début des ensembles de 1000. Inversement, s'il est possible de garder une distance de 1000 autres valeurs entre les répétitions, ce qui force une situation où la séquence se rejoue exactement de la même manière à chaque fois car aucune autre valeur ne s'est produite en dehors de cette limite.

Voici une méthode qui garantit toujours au moins 500 autres valeurs avant qu'une valeur puisse être répétée:

int nrrand(void) {
  static int h[1001];
  static int n = -1;

  if (n < 0) {
    int s = 1;
    for (int i = 0; i < 1001; i++) {
      do {
        s = (s * 1103515245 + 12345) & 1023;
      } while (s >= 1001);
      /* If we used `i` rather than `s` then our early results would be poorly distributed. */
      h[i] = s;
    }
    n = 0;
  }

  int i = rand(500);
  if (i != 0) {
      i = (n + i) % 1001;
      int t = h[i];
      h[i] = h[n];
      h[n] = t;
  }
  i = h[n];
  n = (n + 1) % 1001;

  return i;
}

Lorsque N est supérieur à 1000 et que vous devez tirer K échantillons aléatoires, vous pouvez utiliser un ensemble contenant les échantillons jusqu'à présent. Pour chaque tirage, vous utilisez un échantillonnage de rejet , qui sera une opération "presque" O (1), de sorte que la durée totale de fonctionnement est proche de O (K) avec un stockage O (N).

Cet algorithme se heurte lorsque K est "proche" de N. Cela signifie que le temps d'exécution sera bien pire que O (K). Une solution simple consiste à inverser la logique de sorte que, pour K> N / 2, vous gardiez un enregistrement de tous les échantillons qui n'ont pas encore été tirés. Chaque tirage supprime un échantillon de l'ensemble de rejet.

L'autre problème évident avec l'échantillonnage de rejet est qu'il s'agit du stockage O (N), ce qui est une mauvaise nouvelle si N est dans les milliards ou plus. Cependant, il existe un algorithme qui résout ce problème. Cet algorithme est appelé l'algorithme de Vitter après son inventeur. L'algorithme est décrit ici . L'essentiel de l'algorithme de Vitter est qu'après chaque tirage, vous calculez un saut aléatoire en utilisant une certaine distribution qui garantit un échantillonnage uniforme.

Fisher Yates

for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

C'est en fait O (n-1) car vous n'avez besoin que d'un swap pour les deux derniers
C'est C #

public static List<int> FisherYates(int n)
{
    List<int> list = new List<int>(Enumerable.Range(0, n));
    Random rand = new Random();
    int swap;
    int temp;
    for (int i = n - 1; i > 0; i--)
    {
        swap = rand.Next(i + 1);  //.net rand is not inclusive
        if(swap != i)  // it can stay in place - if you force a move it is not a uniform shuffle
        {
            temp = list[i];
            list[i] = list[swap];
            list[swap] = temp;
        }
    }
    return list;
}

Veuillez consulter ma réponse sur https://stackoverflow.com/a/46807110/8794687

C'est l'un des algorithmes les plus simples qui ont une complexité temporelle moyenne O ( s log s ), s indiquant la taille de l'échantillon. Il existe également des liens vers des algorithmes de table de hachage dont la complexité est supposée être O ( s ).

Quelqu'un a posté "la création de nombres aléatoires dans Excel". J'utilise cet idéal. Créez une structure en 2 parties, str.index et str.ran; Pour 10 nombres aléatoires, créez un tableau de 10 structures. Définissez str.index de 0 à 9 et str.ran sur un nombre aléatoire différent.

for(i=0;i<10; ++i) {
      arr[i].index = i;
      arr[i].ran   = rand();
}

Triez le tableau sur les valeurs de arr [i] .ran. Le str.index est maintenant dans un ordre aléatoire. Ci-dessous le code c:

#include <stdio.h>
#include <stdlib.h>

struct RanStr { int index; int ran;};
struct RanStr arr[10];

int sort_function(const void *a, const void *b);

int main(int argc, char *argv[])
{
   int cnt, i;

   //seed(125);

   for(i=0;i<10; ++i)
   {
      arr[i].ran   = rand();
      arr[i].index = i;
      printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
   printf("\n===================\n");
   for(i=0;i<10; ++i)
   {
      printf("arr[%d] Random  Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   return 0;
}

int sort_function(const void *a, const void *b)
{
   struct RanStr *a1, *b1;

   a1=(struct RanStr *) a;
   b1=(struct RanStr *) b;

   return( a1->ran - b1->ran );
}