从集合中获取X个唯一的数字

1. 制作一个由N个唯一元素(例如0..N-1范围内的整数)组成的数组,将N存储为arraySize和initialArraySize(arraySize=N;initialArraySize=N)
2. 
   2.1如果arraySize为零,则arraySize=initialArraySize
   
   
   2.2将数组[index]与数组[arraySize-1]交换。Swap表示“交换”c=数组[索引];array[index]=数组[arraySize-1];数组[arraySize-1]=c
   
   2.4返回结果。

您将得到一个随机数列表,在用完唯一值之前,这些随机数不会重复。O(1)复杂性。

如果你想从集合{1,…,n}中画出k个不需要替换的随机整数(以得到唯一的数字),你需要的是[n]的随机排列中的前k个元素。生成这种随机排列的最优雅的方法是使用Knuth shuffle。请看这里: http://en.wikipedia.org/wiki/Knuth_shuffle

n位最大周期线性移位反馈寄存器(LFSR)在内部状态被重复之前,将循环通过它的所有(2^n-1)内部状态。LFSR是最大周期LFSR当且仅当由抽头序列加1形成的多项式是模2的本原多项式。

因此,n位最大周期LFSR将为您提供一个(2^n-1)唯一随机数序列,每个随机数都是n位长的。

LFSR非常优雅。

既然你强加了唯一性,那么一个伪随机发生器就足够了,它可以被配置成在你可能需要的时间内不重复序列。例如,一个 LCG