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

Vous pouvez faire ceci:

1. créer une liste, 0..1000.
2. mélangez la liste. (Voir Fisher-Yates shuffle pour une bonne façon de le faire.)
3. renvoie les numéros dans l'ordre de la liste mélangée.

ainsi cela ne nécessite pas une recherche des anciennes valeurs à chaque fois, mais il nécessite encore O(N) pour le mélange initial. Mais Nils souligné dans les commentaires, c'est amorti O (1).

utiliser un registre de rétroaction linéaire Maximal .

il est implémentable dans quelques lignes de C et à l'exécution fait un peu plus que quelques tests/branches, un petit ajout et bit shifting. Ce n'est pas aléatoire, mais ça trompe la plupart des gens.

vous pouvez utiliser un générateur de congruence linéaire . Où m (le module) serait le premier Le plus proche plus grand que 1000. Quand tu auras un numéro hors de portée, prends le suivant. La séquence ne se répète qu'une fois que tous les éléments se sont produits, et vous n'avez pas à utiliser une table. Soyez conscient des inconvénients de ce générateur (y compris le manque d'aléatoire).

vous pouvez utiliser format-préserver le chiffrement pour chiffrer un compteur. Votre compteur va juste de 0 vers le haut, et le cryptage utilise une clé de votre choix pour le transformer en une valeur apparemment aléatoire de quelque radix et largeur que vous voulez. Par exemple: pour l'exemple de cette question: radix 10, Largeur 3.

ont normalement une taille de bloc fixe de 64 ou 128 bits, par exemple. Mais le cryptage de préservation de Format vous permet de prendre un chiffre standard comme AES et faire une plus petite largeur de chiffre, quelle que soit radix et la largeur que vous voulez, avec un algorithme qui est toujours du point de vue cryptographique robuste.

il est garanti de ne jamais avoir de collisions (parce que les algorithmes cryptographiques créent une cartographie 1:1). Il est également réversible (une cartographie bidirectionnelle), de sorte que vous pouvez prendre le nombre résultant et revenir à la valeur de compteur que vous avez commencé avec.

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

AES-FFX est un projet de norme sur la méthode pour y parvenir. J'ai expérimenté avec un code Python basique qui est basé sur L'idée AES-FFX, mais pas entièrement conforme-- voir code Python ici . Il peut par exemple chiffrer un compteur à un nombre décimal aléatoire de 7 chiffres, ou un nombre de 16 bits. Voici un exemple de radix 10, Largeur 3( pour donner un nombre entre 0 et 999 inclus) comme la question se lisait comme suit:

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, changez la clé de cryptage. Chaque clé de cryptage produit une séquence pseudo-aléatoire non répétitive différente.

pour les petits nombres comme 0...1000, la création d'une liste qui contient tous les numéros et le mélange est simple. Mais si l'ensemble des nombres à tirer est très grand il y a une autre façon élégante: vous pouvez construire une permutation de pseudorandom en utilisant une clé et une fonction de hachage cryptographique. Voir l'exemple suivant de code C++-ish:

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;
}

ici, hash est juste une fonction arbitraire pseudo-aléatoire qui mappe une chaîne de caractères à un possible énorme entier non signé. La fonction randperm est une permutation de tous les nombres dans 0...pow(2,bits)-1 en supposant une clé fixe. Cela découle de la construction parce que chaque étape qui change la variable index est réversible. C'est inspiré par un chiffrement Feistel .

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.

initialise le compteur à zéro et l'incrémente sur des appels successifs. XOR le compteur avec le bitmask (choisi au hasard au démarrage, ou fixe) pour générer un nombre psuedorandom. Si vous ne pouvez pas avoir des nombres qui dépassent 1000, n'utilisez pas un masque de bits plus large que 9 bits. (En d'autres termes, le bitmask est un entier ne dépassant pas 511.)

assurez-vous que lorsque le compteur passe 1000, vous le réinitialisez à 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.

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érer des nombres aléatoires mais uniques sans tableaux, listes, permutations ou charge CPU lourde.

Dernière version permet également de définir la plage de numéros, Par exemple, si je veux nombres aléatoires dans la gamme de 0-1073741821.

Je l'ai pratiquement utilisé pour

• MP3 joueur qui joue toutes les chansons au hasard, mais seulement une fois par album/répertoire
• Pixel sage des images vidéo à la dissolution de l'effet (rapide et en douceur)
• la Création d'un secret "bruit" brouillard au-dessus de l'image pour les signatures et les marqueurs (stéganographie)
• IDs D'objet de données pour la sérialisation d'un grand nombre D'objets Java via des bases de données
• Triple Majorité mémoire bits de protection
• Address+value encryption (chaque octet n'est pas seulement encrypté mais aussi déplacé à un nouvel endroit encrypted dans buffer). Cela a vraiment fait cryptanalysis fellows mad sur moi : -)
• texte simple à simple comme cryptage texte crypté pour SMS, e-mails, etc.
• My Texas Hold'em Poker Calculator (THC)
• plusieurs de mes jeux pour simulations, "brassage", "classement 1519140920"
• plus ""

Il est ouvert, gratuit. Lui donner un essai...

Voici un code que j'ai tapé, qui utilise la logique de la première solution. Je sais que c'est "Langue agnostique" mais je voulais juste présenter ceci comme un exemple dans C# au cas où quelqu'un est à la recherche d'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]);
}

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), au besoin.

Note: le Random doit être statique avec la sécurité de fil appliquée.

cette méthode résulte approprié lorsque la limite est haut et vous voulez seulement générer 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 numéros sont générés dans l'ordre croissant, mais vous pouvez mélanger ensuite.

une Autre possibilité:

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

mais, méfiez-vous après 1000 appels, la fonction ne finira jamais donc vous devez faire une sauvegarde.

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

à Partir de ici nous avons à la conception pour un 10 bits PRNG..

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

• utilisez un LFSR Galois pour obtenir le code rapide

voici un exemple de code COBOL avec lequel vous pouvez jouer.

Je peux vous envoyer RANDGEN.exe fichier de sorte que vous pouvez jouer avec elle pour voir si il ne veut que vous voulez.

   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.

disons que vous voulez passer en revue les listes mélangées encore et encore, sans avoir le délai O(n) chaque fois que vous commencez à mélanger à nouveau, dans ce cas, nous pouvons faire ceci:

1. créer 2 listes A et B, avec 0 à 1000, prend 2n espace.

2. Shuffle liste A l'aide de Fisher-Yates, prend n du temps.

3. lors du dessin d'un nombre, faire 1-étape Fisher-Yates shuffle sur l'autre liste.

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

préprocesseur

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

je pense que générateur de congruence linéaire serait la solution la plus simple.

et il y a seulement 3 des restrictions sur la un , c et m valeurs

1. m et c sont relativement premiers,
2. a-1 est divisible par tous les facteurs principaux 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 post a de fausses hypothèses sur les valeurs constantes. Les constantes ci-dessous devraient bien fonctionner pour votre cas

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

X = (1002 * X + 757) mod 1001

la plupart des réponses ici ne garantissent pas qu'ils ne retourneront pas le même nombre 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é à le répéter, mais que naïvement permet 0 à suivre immédiatement après 0 tant qu'ils apparaissent à la fin et le début des séries de 1000. Inversement, alors qu'il est possible de garder une distance de 1000 autres valeurs entre les répétitions, cela force une situation où la séquence se rejoue exactement de la même manière à chaque fois parce qu'il n'y a pas d'autre valeur qui se soit 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;
}

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

cet algorithme entre en collision lorsque K est" proche " de N. cela signifie que le temps d'exécution sera bien pire que O(K). Une solution simple est d'inverser la logique, de sorte que, pour K > N / 2, vous conservez un registre de tous les échantillons qui n'ont pas encore été prélevés. Chaque tirage retire un échantillon du jeu de rejet.

l'autre problème évident avec l'échantillonnage de rejet est que C'est le 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 s'appelle l'algorithme de Vitter d'après son inventeur. L'algorithme est décrit ici . L'essentiel de L'algorithme de Vitter est après chaque tirage, vous calculer une aléatoire sauter en utilisant une certaine distribution qui garantit é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]

il est en fait O (n-1) que vous avez besoin d'un seul swap pour les deux derniers
151980920" 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;
}

la question comment générer efficacement une liste de K entiers non répétitifs entre 0 et une limite supérieure N est liée en tant que duplicata-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 ya un simple tweak de la réponse acceptée.

créer une carte vide non ordonnée (une carte vide ordonnée prendra O (log k) par élément) d'entier en entier-au lieu d'utiliser une carte initialisée tableau. Réglez max à 1000 si c'est le maximum,

1. choisir un nombre aléatoire, r, entre 0 et max.
2. S'assurer que les deux éléments de la Carte r et max existent dans la carte non ordonnée. S'ils n'existent pas les créer avec une valeur égale à leur index.
3. éléments D'échange r et max
4. élément de retour max et décrément max par 1 (si max devient négatif vous avez terminé).
5. retourner à 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/sautée - mais elle générera les mêmes nombres exacts à partir du même PRNG.

s'il vous Plaît voir ma réponse à https://stackoverflow.com/a/46807110/8794687

il s'agit de 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 y a aussi des liens vers des algorithmes de table de hachage. la complexité de who's est supposée être O ( s ).