O（1）中的唯一（非重复）随机数？
我想生成一个0到1000之间的独一无二的随机数字，这个数字永远不会重复（即，6次不会出现两次），但是这并不会像以前的O（N）search那样。 这可能吗？
初始化值为0-1000的1001个整数数组，并将variablesmax设置为数组的当前最大索引（以1000开头）。 在0到max之间select一个随机数r，将位置r处的数字与位置max处的数字进行交换，然后返回位置max处的数字。 最大减1并继续。 当max为0时，将max设置回数组-1的大小并重新开始，而不需要重新初始化数组。
更新：当我回答这个问题时，虽然我自己提出了这个方法，但经过一些研究后，我意识到这是一个名为Durstenfeld-Fisher-Yates或Knuth-Fisher-Yates的Fisher-Yates的修改版本。 由于描述可能有点难以遵循，我在下面提供了一个例子（使用11个元素而不是1001）：
数组从11个元素初始化为array [n] = n开始，max从10：
+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10| +--+--+--+--+--+--+--+--+--+--+--+ ^ max
在每次迭代中，在0和max之间select一个随机数r，交换array [r]和array [max]，返回新数组[max]，并且max递减：
max = 10, r = 3 +--------------------+ vv +--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3| +--+--+--+--+--+--+--+--+--+--+--+ max = 9, r = 7 +-----+ vv +--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3| +--+--+--+--+--+--+--+--+--+--+--+ max = 8, r = 1 +--------------------+ vv +--+--+--+--+--+--+--+--+--+--+--+ | 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3| +--+--+--+--+--+--+--+--+--+--+--+ max = 7, r = 5 +-----+ vv +--+--+--+--+--+--+--+--+--+--+--+ | 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，并且过程可以继续。
你可以这样做：
- 创build一个列表，0..1000。
- 随机清单。 （请参阅Fisher-Yates shuffle ，这是一个很好的方法。）
- 按顺序从混洗列表中返回数字。
所以这不需要每次search旧值，但是对于初始混洗仍然需要O（N）。 但正如尼尔斯在评论中指出的，这是摊销O（1）。
使用最大线性反馈移位寄存器 。
它可以在几行C语言中实现，并且在运行时只需要几个testing/分支，稍加添加和移位即可。 这不是随机的，而是愚弄大多数人。
你可以使用线性同余发生器 。 其中， m （模数）是最接近的大于1000的素数。当你得到一个数字超出范围，就得到下一个数字。 一旦所有的元素都出现了，这个序列只会重复，而且你不必使用表格。 请注意这个生成器的缺点（包括缺乏随机性）。
您可以使用Format-Preserving Encryptionencryption计数器。 你的计数器从0开始向上，encryption使用你select的一个键把它变成一个看似随机的任意的基数和宽度。 例如在这个问题中的例子：基数10，宽度3。
分组密码通常具有例如64或128位的固定块大小。 但是格式保留encryption允许您采用AES等标准密码，并使用仍然具有密码稳健性的algorithm制作更小宽度的密码，无论您想要的基数和宽度如何。
保证不会发生冲突（因为密码algorithm创build1：1映射）。 它也是可逆的（一个双向映射），所以你可以把结果数字返回到你开始的计数器值。
这种技术不需要内存来存储混洗arrays等，这对于内存有限的系统是一个优势。
AES-FFX是实现这一目标的一种标准方法。 我已经尝试了一些基于AES-FFX思想的基本Python代码，尽pipe不完全符合 – 请参阅这里的Python代码 。 它可以例如将计数器encryption成随机的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 ... ...
要获得不同的非重复的伪随机序列，请更改encryption密钥。 每个encryption密钥产生一个不同的非重复的伪随机序列。
对于像0 … 1000这样的低数字，创build一个包含所有数字和混洗的列表是非常简单的。 但是如果要绘制的数字集非常大，还有另外一个优雅的方法：可以使用密钥和密码散列函数来构build伪随机置换。 请参阅以下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只是一些任意的伪随机函数，它将一个string映射到一个可能很大的无符号整数。 函数randperm是假设固定键的0 … pow（2，bits）-1内的所有数字的置换。 这是从build设，因为改变variablesindex每一步是可逆的。 这是由Feistel密码启发的。
你甚至不需要一个数组来解决这个问题。
你需要一个位掩码和一个计数器。
将计数器初始化为零，并在连续调用时递增。 将计数器与位掩码（在启动时随机select或固定）异或以生成伪随机数。 如果数字不能超过1000，则不要使用大于9位的位掩码。 （换句话说，位掩码是一个不大于511的整数。）
确保计数器通过1000时，将其重置为零。 在这个时候，你可以select另一个随机位掩码 – 如果你喜欢 – 以不同的顺序产生相同的一组数字。
你可以使用我在这里描述的Xincrolalgorithm：
http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html
这是一个纯粹的algorithm方法，可以生成随机但唯一的数字，而不需要数组，列表，排列或繁重的CPU负载。
最新版本还可以设置数字的范围，例如，如果我想在0-1073741821的范围内唯一的随机数字。
我已经实际使用它
- MP3播放器随机播放每首歌曲，但每个专辑/目录只有一次
- 像素明智的video帧溶解效果（快速和平滑）
- 在图像上为签名和标记（隐写）创build一个秘密“噪声”
- 用于通过数据库序列化大量Java对象的数据对象ID
- 三倍多数存储位保护
- 地址+值encryption（每个字节不仅仅是encryption的，而且还移动到缓冲区中的一个新的encryption位置）。 这确实使密码分析人员对我生气:-)
- 纯文本到普通文本encryption短信，电子邮件等
- 我的德州扑克计算器（THC）
- 我的几个模拟游戏，“洗牌”，排名
- 更多
它是开放的，免费的。 试一试…
以下是我使用第一个解决scheme的逻辑input的一些代码。 我知道这是“语言不可知的”，但只是想在C＃中提供这个例子，以防有人在寻找一个快速实用的解决scheme。
// 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根据需要，非重复随机数的复杂度为O（n）。
注意：应用线程安全的随机应该是静态的。
这种方法适用于极限高的情况 ，而且只需要生成一些随机数。
#!/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"; }
请注意，数字是按升序生成的，但之后可以随机播放。
另一个可能性：
您可以使用一组标志。 当它已经被选中时，拿走下一个。
但是，千呼万唤，function永远不会结束，所以你一定要保障。
你可以使用一个好的10位随机数发生器 ，扔掉1001到1023，留下0到1000。
从这里我们得到了10位PRNG的devise。
-
10比特，反馈多项式x ^ 10 + x ^ 7 + 1（周期1023）
-
使用Galois LFSR来获得快速的代码
假设你想重复一遍又一遍地重复列表，而不是每次你重新开始拖拽O(n)延迟，那么我们可以这样做：
-
创build2个列表A和B，0到1000，占用
2n空间。 -
洗牌列表A使用Fisher-Yates，需要
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
我认为线性同余发生器是最简单的解决scheme。
而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
这里的大多数答案都不能保证他们不会两次返回相同的号码。 这是一个正确的解决scheme：
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个其他值，这样做会强制每次以完全相同的方式重新播放序列，因为除此之外没有其他值发生。
这里有一个方法总是保证至less有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个随机样本，您可以使用一个包含样本的集合。 对于每个抽奖，你使用拒绝抽样 ，这将是一个“几乎”O（1）的操作，所以总的运行时间接近O（K）与O（N）存储。
当K是“接近”N时，这个algorithm会碰撞。这意味着运行时间将比O（K）差很多。 一个简单的解决方法是反转逻辑，以便对于K> N / 2，logging所有尚未绘制的样本。 每个绘图从剔除集中移除一个样本。
拒收采样的另一个显而易见的问题是它是O（N）存储，如果N在数十亿甚至更多，这是坏消息。 但是，有一个algorithm可以解决这个问题。 本发明人将该algorithm称为Vitteralgorithm。 algorithm在这里描述。 Vitteralgorithm的要点在于，在每次绘制之后，您可以使用一定的分布来计算随机跳跃，以保证均匀采样。
Fisher Yates
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（n））为O（1）启动成本））有一个简单的调整接受的答案。
创build一个空的无序映射（空有序映射将每个元素O（log k））从整数到整数 – 而不是使用初始化数组。 如果最大值设置为1000，
- select一个随机数r，介于0到max之间。
- 确保地图元素r和max都存在于无序地图中。 如果它们不存在，则使用等于其索引的值创build它们。
- 交换元素r和max
- 返回元素的最大值和最大值减1（如果最大负值，你完成）。
- 回到第1步。
与使用初始化数组相比，唯一的区别是元素的初始化被延迟/跳过 – 但是它会从相同的PRNG生成完全相同的数字。
请参阅我的答案在https://stackoverflow.com/a/46807110/8794687
它是平均时间复杂度为O （ s log s ）的最简单algorithm之一， s表示样本大小。 还有一些链接到哈希表algorithm谁的复杂性被声称是O （ S ）。
这里有一些示例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.
