O（1）中唯一的（非重复）随机数？

您可以这样做：

1. 创建一个列表 0..1000。
2. 随机播放列表。（参见 Fisher-Yates shuffle 了解执行此操作的好方法。
3. 从随机列表中按顺序返回数字。

因此，这不需要每次都搜索旧值，但它仍然需要 O（N） 进行初始洗牌。但正如尼尔斯在评论中指出的那样，这是摊销的O（1）。

另一种可能性：

您可以使用标志数组。并采取下一个当它;已经选择了。

但是，请注意，在 1000 次调用后，该功能将永远不会结束，因此您必须采取保护措施。

使用值 0-1000 初始化一个包含 1001 个整数的数组，并将变量 max 设置为数组的当前最大索引（从 1000 开始）。在 0 和 max 之间选择一个随机数 r，将位置 r 处的数字与位置 max 处的数字交换，然后返回位置 max 处的数字。将最大值递减 1 并继续。当 max 为 0 时，将 max 设置回数组的大小 - 1 并重新启动，而无需重新初始化数组。

更新：虽然我在回答这个问题时自己想出了这种方法，但经过一番研究，我意识到这是费舍尔-耶茨的修改版本，称为 Durstenfeld-Fisher-Yates 或 Knuth-Fisher-Yates。由于描述可能有点难以理解，我在下面提供了一个示例（使用 11 个元素而不是 1001 个元素）：

数组从初始化为 array[n] = n 的 11 个元素开始，max 从 10 开始：

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

在每次迭代中，在 0 和 max 之间选择一个随机数 r，交换 array[r] 和 array[max]，返回新的 array[max]，并递减 max：

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|
+--+--+--+--+--+--+--+--+--+--+--+

...

经过 11 次迭代后，数组中的所有数字都已被选中，max == 0，数组元素被洗牌：

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

此时，max 可以重置为 10，该过程可以继续。

您可以使用线性同余生成器。其中（模量）是最接近大于 1000 的素数。当你得到一个超出范围的数字时，就得到下一个。只有在所有元素都发生后，该序列才会重复，并且您不必使用表。不过要注意这个生成器的缺点（包括缺乏随机性）。m

使用最大线性反馈移位寄存器。

它可以在几行 C 语言中实现，在运行时只做几个测试/分支、一些添加和位移。这不是随机的，但它愚弄了大多数人。

你甚至不需要数组来解决这个问题。

您需要一个位掩码和一个计数器。

将计数器初始化为零，并在连续调用时递增计数器。使用位掩码（在启动时随机选择或固定）对计数器进行异或运算，以生成伪随机数。如果数字不能超过 1000，请不要使用宽度超过 9 位的位掩码。（换言之，位掩码是不高于 511 的整数。

确保当计数器超过 1000 时，将其重置为零。此时，您可以选择另一个随机位掩码（如果您愿意），以不同的顺序生成相同的数字集。

您可以使用一个好的 10 位伪随机数生成器，然后扔掉 1001 到 1023，留下 0 到 1000。

从这里我们得到一个 10 位 PRNG 的设计。

• 10 位，反馈多项式 x^10 + x^7 + 1（周期 1023）

• 使用 Galois LFSR 快速获取代码

对于像 0...1000 这样的小数字，创建一个包含所有数字的列表并对其进行洗牌是很简单的。但是，如果要从中抽取的数字集非常大，还有另一种优雅的方法：您可以使用密钥和加密哈希函数构建伪随机排列。请参阅以下 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;
}

这里，只是一些任意伪随机函数，它将字符串映射到一个可能巨大的无符号整数。该函数是 0...pow（2，bits）-1 内所有数字的排列，假设一个固定键。这是从构造中得出的，因为改变变量的每个步骤都是可逆的。这是受Feistel密码的启发。hashrandpermindex

这是我键入的一些代码，它们使用第一个解决方案的逻辑。我知道这是“与语言无关的”，但只是想将其作为 C# 中的一个示例，以防有人正在寻找快速实用的解决方案。

// 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]);
}

当限制很高并且您只想生成几个随机数时，此方法的结果是正确的。

#!/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";
}

请注意，数字是按升序生成的，但您可以先洗牌。

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 根据需要，非重复随机数的复杂度为 O（n）。
注意：Random 应该是静态的，并应用了线程安全。

可以使用格式保留加密来加密计数器。你的计数器只是从 0 开始，加密使用你选择的密钥将其转换为一个看似随机的值，无论你想要什么基数和宽度。例如，对于这个问题中的示例：基数 10，宽度 3。

分组密码通常具有固定的块大小，例如 64 位或 128 位。但是，格式保留加密允许您采用像 AES 这样的标准密码，并使用仍然具有加密鲁棒性的算法来制作更小宽度的密码，无论您想要什么基数和宽度。

保证永远不会发生冲突（因为加密算法会创建 1：1 映射）。它也是可逆的（2 向映射），因此您可以获取结果数字并返回到您开始的计数器值。

这种技术不需要内存来存储随机数组等，这在内存有限的系统上可能是一个优势。

AES-FFX 是实现此目的的一种建议标准方法。我已经尝试了一些基于 AES-FFX 思想的基本 Python 代码，尽管并不完全一致——请参阅此处的 Python 代码。例如，它可以将计数器加密为随机的 7 位十进制数或 16 位数字。以下是基数 10、宽度 3（给出 0 到 999 之间的数字）的示例，如问题所述：

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
...   ...

若要获取不同的非重复伪随机序列，请更改加密密钥。每个加密密钥都会生成不同的非重复伪随机序列。

您可以使用此处描述的 Xincrol 算法：

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

这是一种纯粹的算法方法，可以生成随机但唯一的数字，没有数组、列表、排列或繁重的 CPU 负载。

最新版本还允许设置数字范围，例如，如果我想要 0-1073741821 范围内的唯一随机数。

我实际上已经用它来

• MP3播放器，随机播放每首歌曲，但每个专辑/目录只能播放一次
• 像素级视频帧溶解效果（快速流畅）
• 在签名和标记的图像上创建秘密的“噪点”雾（隐写术）
• 数据对象 ID，用于通过数据库序列化大量 Java 对象
• 三多数存储位保护
• 地址+值加密（每个字节不仅被加密，而且还被移动到缓冲区中的新加密位置）。这真的让密码分析研究员对我生气了：-）
• 纯文本到纯文本，如短信、电子邮件等的加密文本。
• 我的德州扑克计算器 （THC）
• 我的几款模拟游戏，“洗牌”，排名
• 更多

它是开放的，免费的。试一试...

下面是一些您可以使用的示例 COBOL 代码。
我可以向您发送RANDGEN.exe文件，以便您可以使用它，看看它是否确实想要您。

   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.

这里的大多数答案都不能保证它们不会两次返回相同的数字。这是一个正确的解决方案：

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

我不确定约束是否指定得当。人们假设在 1000 个其他输出之后允许一个值重复，但天真地允许 0 紧跟在 0 之后，只要它们都出现在 1000 个集合的末尾和开头。相反，虽然可以在重复之间保持 1000 个其他值的距离，但这样做会强制出现序列每次都以完全相同的方式重播的情况，因为在该限制之外没有发生其他值。

下面是一个方法，在可以重复一个值之前，它始终保证至少 500 个其他值：

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

假设你想一遍又一遍地检查洗牌的列表，而每次重新开始洗牌时都没有延迟，在这种情况下，我们可以这样做：O(n)

1. 创建 2 个列表 A 和 B，其中 0 到 1000 占用空间。2n

2. 使用 Fisher-Yates 随机排列列表 A 需要时间。n

3. 抽取数字时，在另一个列表中进行 1 步费舍尔-耶茨洗牌。

4. 当光标位于列表末尾时，切换到另一个列表。

预处理

cursor = 0

selector = A
other    = B

shuffle(A)

画

temp = selector[cursor]

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

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

return temp

当 N 大于 1000 并且需要绘制 K 个随机样本时，可以使用包含到目前为止的样本的集合。对于每次抽奖，您都使用拒绝采样，这将是“几乎”O（1）操作，因此总运行时间接近O（K），存储为O（N）。

当 K “接近”N 时，该算法会遇到冲突。这意味着运行时间将比 O（K） 差得多。一个简单的解决方法是反转逻辑，以便对于 K > N/2，您可以记录所有尚未绘制的样本。每次抽取都会从剔除集中删除一个样本。

剔除采样的另一个明显问题是它是 O（N） 存储，如果 N 在数十亿或更多，这是个坏消息。但是，有一种算法可以解决这个问题。该算法以其发明者的名字称为 Vitter 算法。此处介绍了该算法。Vitter 算法的要点是，在每次绘制后，您使用一定的分布来计算随机跳跃，从而保证均匀采样。

我认为线性全等生成器是最简单的解决方案。

并且对 A、C 和 M 值只有 3 个限制

1. m 和 c 是相对素数，
2. A-1 可被 m 的所有质因数整除
3. 如果 m 能被 4 整除，则 a-1 能被 4 整除

PS 该方法已经提到过，但帖子对常量值有错误的假设。下面的常量应该适用于您的情况

在您的情况下，您可以使用 、 、a = 1002c = 757m = 1001

X = (1002 * X + 757) mod 1001

费舍尔·耶茨

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

它实际上是 O（n-1），因为最后两个
只需要一个交换，这是 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;
}

问题 如何有效地生成 0 和上限 N 之间的 K 个非重复整数列表被链接为重复项 - 如果您想要每个生成的随机数是 O（1） 的东西（没有 O（n） 启动成本）），可以对接受的答案进行简单的调整。

创建一个空的无序映射（一个空的有序映射将每个元素采用 O（log k））从整数到整数 - 而不是使用初始化的数组。 如果这是最大值，则将 max 设置为 1000，

1. 选择一个介于 0 和最大值之间的随机数 r。
2. 确保映射元素 r 和 max 都存在于无序映射中。如果它们不存在，请使用等于其索引的值创建它们。
3. 交换元素 r 和 max
4. 返回元素 max 并将 max 递减 1（如果 max 变为负数 你完成了）。
5. 返回步骤 1。

与使用初始化数组相比，唯一的区别是元素的初始化被推迟/跳过 - 但它将从相同的 PRNG 生成完全相同的数字。

请在 https://stackoverflow.com/a/46807110/8794687 查看我的回答

它是最简单的算法之一，其平均时间复杂度为 O（s log s），s 表示样本量。那里还有一些指向哈希表算法的链接，其复杂度声称为 O（s）。

有人发帖“在excel中创建随机数”。我正在使用这个理想。 创建一个包含 2 个部分的结构，str.index 和 str.ran; 对于 10 个随机数，创建一个包含 10 个结构的数组。 将 str.index 设置为 0 到 9，将 str.ran 设置为不同的随机数。

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

根据 arr[i].ran 中的值对数组进行排序。 str.index 现在采用随机顺序。 下面是 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 );
}