O (1)中唯一(非重复)随机数？

小开

你可以这样做:

创建一个列表，0. . 1000。
对列表进行洗牌
从洗牌后的列表中按顺序返回数字。

所以这不需要每次都搜索旧的值，但是对于初始的 shuffle 仍然需要 O (N)。但正如尼尔斯在评论中指出的，这是摊销 O (1)。

小开

另一种可能性是:

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

但是，当心1000次调用之后，这个函数将永远不会结束，所以您必须做一个保护措施。

小开

最佳答案

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

更新: 尽管当我回答这个问题的时候我自己想出了这个方法，经过一些研究我意识到这是一个被称为 Durstenfeld-Fisher-Yates 或 Knuth-Fisher-Yates 的 Fisher-Yates的修改版本。由于描述可能有点难以理解，我在下面提供了一个示例(使用11个元素而不是1001) :

Array 从初始化为 Array [ n ] = n 的11个元素开始，max 从10开始:

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

在每次迭代中，在0和 max 之间选择一个随机数 r，数组[ r ]和数组[ max ]交换，返回新的数组[ 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|
+--+--+--+--+--+--+--+--+--+--+--+

此时，最大值可以重置为10，这个过程可以继续。

小开

你可以用线性同余方法。其中 m(模)将是最接近的质数大于1000。当你得到一个超出范围的数字，只是得到下一个。序列只有在所有元素都出现之后才会重复，而且您不必使用表。但是要注意这个生成器的缺点(包括缺乏随机性)。

小开

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

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

小开

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

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

将计数器初始化为零，并在连续调用时递增。使用位掩码 XOR 计数器(在启动时随机选择或固定)来生成一个假随机数。如果数字不能超过1000，就不要使用宽度超过9位的位掩码。(换句话说，位掩码是一个不高于511的整数。)

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

小开

您可以使用具有10位的良好伪随机数发生器伪随机数发生器，抛弃1001到1023，留下0到1000。

从给你我们得到了一个10位 PRNG 的设计..。

10位，反馈多项式 x ^ 10 + x ^ 7 + 1(周期1023)
使用伽罗瓦 LFSR 获得快速代码

小开

对于像0... 1000这样的小数字，创建一个包含所有数字的列表并进行洗牌是很直接的。但是，如果要从一组非常大的数字中提取，还有另一种优雅的方法: 你可以使用一个键和一个密码杂凑函数构建一个伪随机排列。请参见下面 C + + 风格的示例伪代码:

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

在这里，hash只是一个任意的伪随机函数，它将一个字符串映射到一个可能很大的无符号整数。函数 randperm是0... pow (2，bit)-1内所有数字的排列，假设键是固定的。这是因为改变变量 index的每一步都是可逆的。这是受到费斯特密码的启发。

小开

下面是我键入的一些代码，它们使用了第一个解决方案的逻辑。我知道这是“语言不可知论”，但只是想在 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();
}

根据需要，非重复随机数的复杂度为 O (n)。
注意: 随机应该是静态的，应用线程安全。

小开

可以使用格式保存加密对计数器进行加密。你的计数器只是从0开始，加密使用你选择的一个密钥将它转换成你想要的基数和宽度的一个看似随机的值。例如这个问题中的例子: 基数10，宽度3。

分组密码通常有固定的分组大小，例如64或128位。但是格式保持加密允许你使用像 AES 这样的标准密码，并且使用一种仍然具有密码学健壮性的算法，制作一个宽度更小的密码，不管你想要的基数和宽度是多少。

它保证永远不会有冲突(因为加密算法创建1:1的映射)。它也是可逆的(一个双向映射) ，因此您可以获取结果数字并返回到您开始使用的计数器值。

这种技术不需要内存来存储混合数组等，这对于内存有限的系统来说是一个优势。

AES-FFX 是实现这一目标的一种标准方法。我已经试验了一些基于 AES-FFX 思想的基本 Python 代码，尽管它们并不完全符合在这里查看 Python 代码。它可以将计数器加密为一个看似随机的7位十进制数或16位数。下面是基数10的一个例子，宽度3(给出一个介于0和999之间的数字) ，正如问题所述:

要获得不同的非重复伪随机序列，请更改加密密钥。每个加密密钥产生一个不同的非重复伪随机序列。

小开

你可以使用我在这里描述的新克罗尔算法:

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

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

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

我几乎用它来

MP3播放器，随机播放每首歌曲，但每张专辑/目录只播放一次
像素级视频帧溶解效果(快速、平滑)
为签名和标记(隐写术)创建一个秘密的“噪音”图像雾
通过数据库序列化大量 Java 对象的数据对象 ID
三重多数内存位保护
地址 + 值加密(每个字节不仅被加密，而且还被移动到缓冲区中一个新的加密位置)。这真的让密码分析家们对我很生气: -)
为短信、电子邮件等进行文本加密。
我的德州扑克计算器(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)延迟，在这种情况下，我们可以这样做:

创建2个列表 A 和 B，0到1000，占用 2n空间。
洗牌列表 A 使用费舍尔-耶茨，需要 n时间。
当抽取一个数字时，在另一个列表上进行一步 Fisher-Yates 洗牌。
当光标位于列表末尾时，切换到另一个列表。

预处理

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 (N)存储的总运行时间接近 O (K)。

当 K“接近”N 时，该算法会遇到冲突。这意味着运行时间将比 O (K)糟糕得多。一个简单的修复方法是逆转逻辑，这样，对于 K > N/2，就可以记录所有尚未绘制的样本。每次抽取从拒绝集中移除一个样品。

拒绝采样的另一个明显的问题是，它是 O (N)存储，如果 N 是数十亿或更多，这是一个坏消息。但是，有一种算法可以解决这个问题。这个算法以其发明者的名字命名为维特算法。该算法被描述为给你。维特算法的要点是，在每次抽样之后，你使用一定的分布来计算一个随机跳过，这样可以保证统一的抽样。

小开

我认为线性同余方法是最简单的解决方案。

对于  a 、  c 和  m 值只有3个限制

M 和  c 是相对的质数,
A-1 可被 m 的所有素因子整除
A-1 可被  4 整除，如果  m 可被 4整除

PS 这个方法已经提到过了，但是帖子对于常数值有一个错误的假设。下面的常数应该可以很好地满足您的需要

在你的情况下，你可以使用 a = 1002，c = 757，m = 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)每个元素)从整数到整数-而不是使用一个初始化的数组。如果最大值是1000，则将最大值设置为1000,

选择一个介于0和最大值之间的随机数 r。
确保无序映射中同时存在映射元素 r 和 max。如果它们不存在，则创建它们的值等于它们的索引。
交换元素 r 和 max
返回元素 max 并将 max 减1(如果 max 变为负值) 你就完了)。
回到第一步。

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

小开

请在 https://stackoverflow.com/a/46807110/8794687上看到我的答案

它是最简单的算法之一，具有平均时间复杂度哦(是的 log 是的) ，即表示样本大小的是的。还有一些链接到哈希表算法谁的复杂性声称是哦(是的)。

小开

有人发布了“在 excel 中创建随机数”。我正在使用这个理想状态。创建一个由 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 );
}