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

我想生成0到1000之间永远不会重复的唯一随机数(即6不会出现两次),但这并不是像以前的值的O(N)搜索那样.这可能吗？

1> Robert Gambl..：

---

初始化一个1001个整数的数组,值为0-1000,并将变量max设置为数组的当前最大索引(从1000开始).选择0到最大值之间的随机数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之间选择随机数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|
+--+--+--+--+--+--+--+--+--+--+--+

此时,max可以重置为10,并且该过程可以继续.

---

@Peter Rounce:我想不是; 这对我来说就像Fisher Yates算法一样,也引用了Jeff的帖子(作为好人).

---

杰夫关于洗牌的帖子表明这不会返回好的随机数字.http://www.codinghorror.com/blog/archives/001015.html

---

我有点困惑,你不得不执行`N`迭代(本例中为11)以获得所需的结果每次都意味着它是'O(n)`？因为你需要进行`N`迭代以从相同的初始状态获得'N!'组合,否则你的输出将只是N个状态之一.

---

@robert:我只是想指出它不会像问题的名称那样产生"O(1)中的唯一随机数".

---

@mikera:同意,虽然在技术上,如果您使用固定大小的整数整个列表可以为O(1)产生(具有大的常数,即2 ^ 32).此外,出于实际目的,"随机"的定义很重要 - 如果您真的想要使用系统的熵池,那么限制是随机位的计算而不是计算本身,在这种情况下,n log n是相关的再次.但是在可能的情况下你将使用(相当于)/ dev/urandom而不是/ dev/random,你会回到'实际上'O(n).

2> Chris Jester..：

---

你可以这样做:

创建一个列表,0..1000.

洗牌清单.(请参阅Fisher-Yates shuffle以获得这样做的好方法.)

从洗牌列表中按顺序返回数字.

因此,这不需要每次都搜索旧值,但它仍然需要O(N)用于初始shuffle.但正如尼尔斯在评论中指出的那样,这是摊销的O(1).

---

@Just Some Guy N = 1000,所以你说的是O(N/N)是O(1)

---

以这种方式考虑,如果它是恒定的时间,10个随机数将花费相同的时间,而100亿.但由于采取了O(n)的改组,我们知道这不是真的.

---

现在,我有充分的理由去做!http://meta.stackoverflow.com/q/252503/13

3> plinth..：

---

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

它可以在几行C中实现,并且在运行时只需要几个测试/分支,一点点添加和位移.这不是随意的,但它愚弄了大多数人.

---

"这不是随意的,但它会欺骗大多数人".这适用于所有伪随机数生成器以及该问题的所有可行答案.但大多数人都不会考虑它.所以省略这个说明可能会导致更多的赞成......

---

@bobobobo:O(1)内存是原因.

---

Nit:它是O(log N)内存.

---

使用该方法,如何生成数字,假设介于0和800000之间？有些人可能会使用LFSR,其周期为1048575(2 ^ 20 - 1),如果数字超出范围,则获得下一个,但这不会有效.

4> Paul de Vrie..：

---

您可以使用线性同余生成器.其中m(模数)是最接近的大于1000的素数.当你得到一个超出范围的数字时,只需得到下一个.只有在发生所有元素后,序列才会重复,您不必使用表格.请注意这个发生器的缺点(包括缺乏随机性).

5> Craig McQuee..：

---

您可以使用格式保留加密来加密计数器.你的计数器从0开始向上,加密使用你选择的一个键将它变成你想要的任何基数和宽度的看似随机的值.例如,对于此问题中的示例:基数10,宽度3.

分组密码通常具有固定的块大小,例如64或128位.但是格式保留加密允许您采用AES之类的标准密码,并使用一种仍然具有加密稳健性的算法制作一个小宽度密码,无论您需要什么基数和宽度.

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

该技术不需要存储器来存储混洗阵列等,这在具有有限存储器的系统上可能是有利的.

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

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

---

+1.当正确实现时,使用具有随机均匀选择的密钥的安全分组密码,使用该方法生成的序列在计算上将与真正的随机混洗无法区分.也就是说,无法通过测试所有可能的块密码密钥并查看它们中的任何一个是否生成相同的输出,明显更快地区分此方法的输出与真正的随机混洗.对于具有128位密钥空间的密码,这可能超出了当前人类可用的计算能力; 使用256位密钥,它可能会永远保持这种状态.

---

@ivan_pozdeev并非FPE必须实现特定的静态映射,或者"返回的组合完全由第一个数字定义".由于配置参数远大于第一个数字(只有一千个状态)的大小,因此应该有多个序列以相同的初始值开始,然后继续执行不同的后续值.任何现实的发电机都无法覆盖整个可能的排列空间; 当OP没有要求时,不值得提出失败模式.

6> sellibitze..：

---

对于像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密码的启发.

7> 小智..：

---

你可以使用我在这里描述的Xincrol算法:

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

这是一种生成随机但唯一数字的纯算法方法,无需数组,列表,排列或繁重的CPU负载.

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

我几乎用它了

随机播放每首歌曲的MP3播放器,但每张专辑/目录只播放一次

像素智能视频帧解析效果(快速平滑)

在图像上为签名和标记创建一个秘密的"噪音"雾(隐写术)

用于通过数据库序列化大量Java对象的数据对象ID

三重多数存储位保护

地址+值加密(每个字节不仅加密,而且还移动到缓冲区中的新加密位置).这真的让密码分析研究员对我很生气:-)

纯文本到普通像加密文本加密短信,电子邮件等.

我的德州扑克计算器(THC)

我的几个模拟游戏,"洗牌",排名

更多

它是开放的,免费的.试试看...

8> Max..：

---

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

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

将计数器初始化为零,并在连续调用时递增计数器.使用位掩码(在启动时随机选择或固定)对计数器进行异或,以生成伪随机数.如果您的数字不能超过1000,请不要使用大于9位的位掩码.(换句话说,位掩码是一个不高于511的整数.)

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

---

那比LFSR愚弄的人少.