我想生成 0 到 1000 之间的唯一随机数，这些随机数永远不会重复（即 6 不会出现两次），但这不会诉诸于对先前值进行 O(N) 搜索之类的方法。这可能吗？
dicroce
问问题
104510 次
22 回答
257
使用值 0-1000 初始化一个包含 1001 个整数的数组，并将变量 max 设置为数组的当前最大索引（从 1000 开始）。选择一个介于 0 和 max 之间的随机数 r，将位置 r 处的数字与位置 max 处的数字交换，然后返回当前位置 max 处的数字。将 max 减 1 并继续。当 max 为 0 时，将 max 设置回数组的大小 - 1 并重新开始，无需重新初始化数组。
更新： 虽然我在回答这个问题时自己想出了这个方法，但经过一些研究，我意识到这是一个修改版本的Fisher-Yates，称为 Durstenfeld-Fisher-Yates 或 Knuth-Fisher-Yates。由于描述可能有点难以理解，我在下面提供了一个示例（使用 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，并且可以继续该过程。
于 2008-10-12T20:57:02.080 回答
72
你可以这样做：
- 创建一个列表，0..1000。
- 随机播放列表。（请参阅Fisher-Yates shuffle了解执行此操作的好方法。）
- 从打乱的列表中按顺序返回数字。
所以这不需要每次都搜索旧值，但它仍然需要 O(N) 进行初始洗牌。但正如 Nils 在评论中指出的那样，这是摊销 O(1)。
于 2008-10-12T20:37:24.413 回答
63
使用最大线性反馈移位寄存器。
它可以用几行 C 语言来实现，并且在运行时只做几个测试/分支、一点加法和位移。这不是随机的，但它欺骗了大多数人。
于 2008-10-14T18:14:59.677 回答
28
您可以使用Format-Preserving Encryption来加密计数器。您的计数器只是从 0 向上，加密使用您选择的密钥将其转换为您想要的任何基数和宽度的看似随机的值。例如，对于这个问题中的示例：基数 10，宽度 3。
块密码通常具有固定的块大小，例如 64 或 128 位。但是 Format-Preserving Encryption 允许您使用像 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
... ...
要获得不同的非重复伪随机序列，请更改加密密钥。每个加密密钥产生一个不同的非重复伪随机序列。
于 2013-04-19T04:33:02.900 回答
23
您可以使用 A Linear Congruential Generator。其中m（模数）将是大于 1000 的最接近的素数。当您得到一个超出范围的数字时，只需获取下一个。该序列只会在所有元素都发生后重复，您不必使用表格。但是请注意此生成器的缺点（包括缺乏随机性）。
于 2008-10-12T21:46:14.460 回答
8
对于像 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 密码启发的。
于 2010-06-22T15:11:01.657 回答
6
您可以使用此处描述的我的 Xincrol 算法：
http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html
这是一种生成随机但唯一数字的纯算法方法，无需数组、列表、排列或繁重的 CPU 负载。
最新版本还允许设置数字范围，例如，如果我想要 0-1073741821 范围内的唯一随机数。
我实际上已经将它用于
- MP3 播放器随机播放每首歌曲，但每个专辑/目录仅播放一次
- 逐像素视频帧溶解效果（快速流畅）
- 为签名和标记（隐写术）在图像上创建秘密“噪声”雾
- 用于通过数据库序列化大量 Java 对象的数据对象 ID
- 三重多数内存位保护
- 地址+值加密（每个字节不仅被加密，而且被移动到缓冲区中一个新的加密位置）。这真的让密码分析人员对我很生气:-)
- 纯文本到纯文本加密，用于 SMS、电子邮件等。
- 我的德州扑克计算器 (THC)
- 我的几款游戏用于模拟，“洗牌”，排名
- 更多的
它是开放的，免费的。试试看...
于 2013-12-19T18:40:35.270 回答
6
我认为线性同余生成器将是最简单的解决方案。
并且对a、c和m值只有 3 个限制
- m和c互质，
- a-1能被m的所有素因子整除
- 如果m能被4整除，则a-1能被4整除
PS该方法已经提到过，但是帖子对常数值有错误的假设。下面的常量应该适用于您的情况
在您的情况下，您可以使用a = 1002, c = 757,m = 1001
X = (1002 * X + 757) mod 1001
于 2016-12-17T04:22:27.257 回答
5
你甚至不需要一个数组来解决这个问题。
你需要一个位掩码和一个计数器。
将计数器初始化为零并在连续调用时将其递增。将计数器与位掩码（在启动时随机选择或固定）进行异或运算以生成伪随机数。如果不能有超过 1000 的数字，请不要使用超过 9 位的位掩码。（换句话说，位掩码是不大于 511 的整数。）
确保当计数器超过 1000 时，将其重置为零。此时，您可以选择另一个随机位掩码（如果您愿意）以不同的顺序生成相同的数字集。
于 2009-01-03T05:55:29.303 回答
3
这是我使用第一个解决方案的逻辑键入的一些代码。我知道这是“语言不可知论”，但只是想在 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]);
}
于 2010-08-25T17:49:40.260 回答
3
当限制很高并且您只想生成几个随机数时，此方法的结果是合适的。
#!/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";
}
请注意，数字是按升序生成的，但之后您可以随机播放。
于 2012-01-19T18:19:36.347 回答
3
问题如何有效地生成介于 0 和上限 N 之间的 K 个非重复整数的列表被链接为重复项 - 如果您想要每个生成的随机数为 O(1) 的东西（没有 O(n)启动成本））对已接受的答案进行了简单的调整。
创建一个从整数到整数的空无序映射（一个空的有序映射每个元素需要 O(log k)） - 而不是使用初始化数组。如果这是最大值，请将最大值设置为 1000，
- 选择一个介于 0 和最大值之间的随机数 r。
- 确保地图元素 r 和 max 都存在于无序地图中。如果它们不存在，则使用等于它们的索引的值创建它们。
- 交换元素 r 和 max
- 返回元素最大值并将最大值减 1（如果最大值变为负数，则完成）。
- 返回步骤 1。
与使用初始化数组相比，唯一的区别是元素的初始化被推迟/跳过——但它会从同一个 PRNG 生成完全相同的数字。
于 2017-07-03T11:29:52.957 回答
2
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) 复杂度。
注意：随机应该是静态的，并且应用了线程安全。
于 2012-05-23T19:43:18.360 回答
2
这是一些您可以使用的示例 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.
于 2015-02-22T02:29:42.330 回答
2
假设您想一遍又一遍地检查已洗牌的列表，而不会在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
于 2016-04-27T20:33:16.183 回答
1
另一种可能性：
您可以使用一组标志。当它已经被选中时，再拿下一个。
但是，请注意，调用 1000 次后，该功能将永远不会结束，因此您必须做好保护措施。
于 2008-10-12T20:38:25.660 回答
1
这里的大多数答案都不能保证它们不会两次返回相同的数字。这是一个正确的解决方案：
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;
}
于 2015-06-02T04:32:42.903 回答
1
当 N 大于 1000 并且您需要抽取 K 个随机样本时，您可以使用包含迄今为止样本的集合。对于每次抽奖，您都使用拒绝采样，这将是一个“几乎”O(1) 操作，因此总运行时间接近 O(K)，存储时间为 O(N)。
当 K “接近” N 时，该算法会发生冲突。这意味着运行时间将比 O(K) 差很多。一个简单的解决方法是颠倒逻辑，以便在 K > N/2 时，记录所有尚未抽取的样本。每次抽取都会从拒绝集中删除一个样本。
拒绝采样的另一个明显问题是它是 O(N) 存储，如果 N 达到数十亿或更多，这是个坏消息。但是，有一种算法可以解决这个问题。这个算法在它的发明者之后被称为维特算法。该算法在此处描述。Vitter 算法的要点是，在每次抽签后，您使用确保均匀采样的特定分布计算随机跳跃。
于 2016-11-22T08:26:07.297 回答
0
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;
}
于 2017-03-01T20:42:45.207 回答
0
请在https://stackoverflow.com/a/46807110/8794687查看我的回答
它是最简单的算法之一，平均时间复杂度为O ( s log s )，s表示样本大小。还有一些链接到哈希表算法，其复杂性据称为O ( s )。
于 2017-10-30T05:02:32.410 回答
-1
有人发布“在 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 );
}
于 2019-11-01T21:32:31.463 回答