O（1）中的唯一（非重复）随机数？
我想生成 0 到 1000 之间的唯一随机数，这些随机数永远不会重复（即 6 不会出现两次），但这不会诉诸于对先前值进行 O(N) 搜索之类的方法。这可能吗？
O(n)），那么下面的许多答案都是错误的，包括已接受的答案。
使用值 0-1000 初始化一个包含 1001 个整数的数组，并将变量 max 设置为数组的当前最大索引（从 1000 开始）。选择一个介于 0 和 max 之间的随机数 r，将位置 r 处的数字与位置 max 处的数字交换，然后返回当前位置 max 处的数字。将 max 减 1 并继续。当 max 为 0 时，将 max 设置回数组的大小 - 1 并重新开始，无需重新初始化数组。
更新：虽然我在回答问题时自己想出了这种方法，但经过一些研究后，我意识到这是 Fisher-Yates 的修改版本，称为 Durstenfeld-Fisher-Yates 或 Knuth-Fisher -耶茨。由于描述可能有点难以理解，我在下面提供了一个示例（使用 11 个元素而不是 1001 个）：
数组从初始化为 array[n] = n 的 11 个元素开始，最大值从 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，并且可以继续该过程。
你可以这样做：
创建一个列表，0..1000。随机播放列表。 （请参阅 Fisher-Yates shuffle 以获得这样做的好方法。）从 shuffled 列表中按顺序返回数字。
所以这不需要每次都搜索旧值，但它仍然需要 O(N) 进行初始洗牌。但正如 Nils 在评论中指出的那样，这是摊销 O(1)。
使用 Maximal Linear Feedback Shift Register。
它可以用几行 C 语言来实现，并且在运行时只做几个测试/分支、一点加法和位移。这不是随机的，但它欺骗了大多数人。
您可以使用 Format-Preserving Encryption 来加密计数器。您的计数器只是从 0 向上，加密使用您选择的密钥将其转换为您想要的任何基数和宽度的看似随机的值。例如，对于这个问题中的示例：基数 10，宽度 3。
块密码通常具有固定的块大小，例如 64 或 128 位。但是 Format-Preserving Encryption 允许您采用像 AES 这样的标准密码，并使用您想要的任何基数和宽度的更小宽度的密码，并使用一种在密码学上仍然健壮的算法。
保证永远不会发生冲突（因为密码算法创建 1:1 映射）。它也是可逆的（2 路映射），因此您可以获取结果数字并返回您开始使用的计数器值。
这种技术不需要内存来存储洗牌数组等，这在内存有限的系统上可能是一个优势。
AES-FFX 是实现此目的的一种建议标准方法。我已经尝试了一些基于 AES-FFX 思想的基本 Python 代码，虽然不完全符合 - see Python code here。例如，它可以将计数器加密为看似随机的 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
... ...
要获得不同的非重复伪随机序列，请更改加密密钥。每个加密密钥产生一个不同的非重复伪随机序列。
k 的值永远不会同时出现）。
k？
1,2,...,N，但仍然是不变的。然后从这个序列中一个一个地提取数字。 k 是选择的值的数量（OP 没有为它指定一个字母，所以我不得不介绍一个）。
您可以使用 A Linear Congruential Generator。其中 m（模数）将是大于 1000 的最接近的素数。当您得到一个超出范围的数字时，只需获取下一个。该序列只会在所有元素都发生后重复，您不必使用表格。但是请注意此生成器的缺点（包括缺乏随机性）。
k 的数字永远不会一起出现）。
对于像 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;
}
这里，hash 只是一些任意的伪随机函数，它将字符串映射到一个可能很大的无符号整数。函数 randperm 是 0...pow(2,bits)-1 内所有数字的排列，假设一个固定键。这是从构造中得出的，因为改变变量 index 的每一步都是可逆的。这是受 Feistel cipher 启发的。
hash() 是一个安全的伪随机函数，这个构造将可证明（Luby & Rackoff，1988）产生一个 pseudorandom permutation，它不能与真正的随机洗牌区分开来比对整个密钥空间的详尽搜索更少的努力，整个密钥空间是密钥长度的指数。即使对于大小合理的密钥（例如 128 位），这也超出了地球上可用的总计算能力。
hash( key + "/" + int2str(temp) ) 构造，其安全性反过来可以证明可以降低到底层哈希压缩函数的安全性。另外, 使用 HMAC 可能会降低某人错误地尝试将此构造与不安全的非加密哈希函数一起使用的可能性。）
您可以使用此处描述的我的 Xincrol 算法：
http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html
这是一种生成随机但唯一数字的纯算法方法，无需数组、列表、排列或繁重的 CPU 负载。
最新版本还允许设置数字范围，例如，如果我想要 0-1073741821 范围内的唯一随机数。
我实际上已经将它用于
MP3 播放器随机播放每首歌曲，但每个专辑/目录仅播放一次
逐像素视频帧溶解效果（快速流畅）
为签名和标记（隐写术）在图像上创建秘密“噪声”雾
用于通过数据库序列化大量 Java 对象的数据对象 ID
三重多数内存位保护
地址+值加密（每个字节不仅被加密，而且被移动到缓冲区中一个新的加密位置）。这真的让密码分析人员对我很生气:-)
纯文本到纯文本加密，用于 SMS、电子邮件等。
我的德州扑克计算器 (THC)
我的几款游戏用于模拟，“洗牌”，排名
更多的
它是开放的，免费的。试试看...
k 的值永远不会同时出现）。
我认为 Linear congruential generator 将是最简单的解决方案。
https://i.stack.imgur.com/rFB37.png
并且对 a、c 和 m 值只有 3 个限制
和 c 互质，a-1 能被 m 的所有质因数整除 如果 m 能被 4 整除，a-1 能被 4 整除
PS该方法已经提到过，但是帖子对常数值有错误的假设。下面的常量应该适用于您的情况
在您的情况下，您可以使用 a = 1002、c = 757、m = 1001
X = (1002 * X + 757) mod 1001
你甚至不需要一个数组来解决这个问题。
你需要一个位掩码和一个计数器。
将计数器初始化为零并在连续调用时将其递增。将计数器与位掩码（在启动时随机选择或固定）进行异或运算以生成伪随机数。如果不能有超过 1000 的数字，请不要使用超过 9 位的位掩码。 （换句话说，位掩码是不大于 511 的整数。）
确保当计数器超过 1000 时，将其重置为零。此时，您可以选择另一个随机位掩码（如果您愿意）以不同的顺序生成相同的数字集。
这是我使用第一个解决方案的逻辑键入的一些代码。我知道这是“语言不可知论”，但只是想在 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";
}
请注意，数字是按升序生成的，但之后您可以随机播放。
(top,n)=(100,10)：(0.01047705, 0.01044825, 0.01041225, ..., 0.0088324, 0.008723, 0.00863635)。我在 Python 中进行了测试，因此数学上的细微差别可能会在这里起作用（我确实确保用于计算 r 的所有操作都是浮点数）。
问题 How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N 被链接为重复项 - 如果您想要每个生成的随机数 O(1) 的东西（没有 O(n) 启动成本），则可以对已接受的答案进行简单调整。
从整数到整数创建一个空的无序映射（一个空的有序映射每个元素需要 O(log k)） - 而不是使用初始化数组。如果这是最大值，请将最大值设置为 1000，
选择一个介于 0 和最大值之间的随机数 r。确保地图元素 r 和 max 都存在于无序地图中。如果它们不存在，则使用等于它们的索引的值创建它们。交换元素 r 和 max 返回元素 max 并将 max 减 1（如果 max 变为负数，则完成）。返回步骤 1。
与使用初始化数组相比的唯一区别是元素的初始化被推迟/跳过 - 但它将从相同的 PRNG 生成完全相同的数字。
您可以使用具有 10 位的良好 pseudo-random number generator 并丢弃 1001 到 1023 留下 0 到 1000。
从 here 我们得到 10 位 PRNG 的设计..
10 位，反馈多项式 x^10 + x^7 + 1（周期 1023）
使用 Galois LFSR 获取快速代码
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) 复杂度。注意：随机应该是静态的，并且应用了线程安全。
这是一些您可以使用的示例 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.
假设您想一遍又一遍地检查已洗牌的列表，而每次重新开始洗牌时都没有 O(n) 延迟，在这种情况下，我们可以这样做：
创建 2 个列表 A 和 B，从 0 到 1000，占用 2n 空间。使用 Fisher-Yates 对列表 A 进行洗牌，需要 n 时间。绘制数字时，在另一个列表上执行 1 步 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
[1,3,4,5,2] 将产生与改组 [1,2,3,4,5] 相同的结果。
另一种可能性：
您可以使用一组标志。当它已经被选中时，再拿下一个。
但是，请注意，调用 1000 次后，该功能将永远不会结束，因此您必须做好保护措施。
这里的大多数答案都不能保证它们不会两次返回相同的数字。这是一个正确的解决方案：
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;
}
当 N 大于 1000 并且您需要抽取 K 个随机样本时，您可以使用包含迄今为止样本的集合。对于每次绘制，您使用 rejection sampling，这将是一个“几乎”O(1) 操作，因此总运行时间接近 O(K)，存储空间为 O(N)。
当 K “接近” N 时，该算法会发生冲突。这意味着运行时间将比 O(K) 差很多。一个简单的解决方法是颠倒逻辑，以便在 K > N/2 时，记录所有尚未抽取的样本。每次抽取都会从拒绝集中删除一个样本。
拒绝采样的另一个明显问题是它是 O(N) 存储，如果 N 达到数十亿或更多，这是个坏消息。但是，有一种算法可以解决这个问题。这个算法在它的发明者之后被称为维特算法。该算法描述为here。 Vitter 算法的要点是，在每次抽签后，您使用确保均匀采样的特定分布计算随机跳跃。
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;
}
请在 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 );
}
关注公众号
不定期副业成功案例分享
N次迭代（在本例中为 11 次）才能获得所需的结果，这是否意味着它是O(n)？因为您需要进行N次迭代才能从相同的初始状态获得N!个组合，否则您的输出将只是 N 个状态之一。