代码之家 › 专栏 › 技术社区 › David van Dugteren

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

unique set theory random algorithm

4

David van Dugteren · 技术社区 · 15 年前

在我需要随机唯一数的时候,我使用while循环检查它是否是唯一的,看看我以前是否使用过随机数。

所以看起来像:

int n = getRandomNumber % [Array Size];

for each ( Previously used n in list)
    Check if I've used n before, if I have...try again.

我现在不能思考,所以也许一旦我喝了一些咖啡因,我的大脑就会随着咖啡引起的高智商而兴奋起来。

4 回复 | 直到 15 年前

1

3

SigTerm 15 年前

制作一个由N个唯一元素(例如0..N-1范围内的整数)组成的数组,将N存储为arraySize和initialArraySize(arraySize=N;initialArraySize=N)
2.1如果arraySize为零,则arraySize=initialArraySize

2.2将数组[index]与数组[arraySize-1]交换。Swap表示“交换”c=数组[索引];array[index]=数组[arraySize-1];数组[arraySize-1]=c

2.4返回结果。

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

2

5

Aaron 15 年前

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

3

1

M.A. Hanin 15 年前

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

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

LFSR非常优雅。

4

0

joe snyder 15 年前

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