对于从50中选6个数字,我不太确定是否需要担心效率,因为重复出现的机会相对较低(根据我的草稿计算,总体上约为30%)。你可以很容易地记住之前生成的数字并将其丢弃,类似以下的伪代码:
n[0] = rnd(50)
for each i in 1..5:
n[i] = n[0]
while n[1] == n[0]:
n[1] = rnd(50)
while n[2] == any of (n[0], n[1]):
n[2] = rnd(50)
while n[3] == any of (n[0], n[1], n[2]):
n[3] = rnd(50)
while n[4] == any of (n[0], n[1], n[2], n[3]):
n[4] = rnd(50)
while n[5] == any of (n[0], n[1], n[2], n[3], n[4]):
n[5] = rnd(50)
然而,随着选取范围从6-from-50扩展至48-from-50或6-from-6,会出现问题。因为随着可用数字的池子越来越小,重复的概率变得越来越高。对于这种情况,一个非常有效的解决方案是使用Fisher-Yates算法,它可以给你一个值的子集,并且零概率出现重复(并且没有不必要的预先排序)。
dim n[50] // gives n[0] through n[9]
for each i in 0..49:
n[i] = i // initialise them to their indexes
nsize = 50 // starting pool size
do 6 times:
i = rnd(nsize) // give a number between 0 and nsize-1
print n[i]
nsize = nsize - 1 // these two lines effectively remove the used number
n[i] = n[nsize]
通过从池中随机选择一个数字,用该池的顶部数字替换它,然后缩小池的大小,您可以获得一次洗牌而无需担心大量的初始交换。
如果数字很高,这很重要,因为它不会引入不必要的启动延迟。
例如,考虑以下基准测试,选择10个数字中的10个:
<------ n[] ------>
0 1 2 3 4 5 6 7 8 9 nsize rnd(nsize) output
------------------- ----- ---------- ------
0 1 2 3 4 5 6 7 8 9 10 4 4
0 1 2 3 9 5 6 7 8 9 7 7
0 1 2 3 9 5 6 8 8 2 2
0 1 8 3 9 5 6 7 6 6
0 1 8 3 9 5 6 0 0
5 1 8 3 9 5 2 8
5 1 9 3 4 1 1
5 3 9 3 0 5
9 3 2 1 3
9 1 0 9
当您执行代码时,可以观察到所使用的池逐渐减少。由于您始终在用未使用的元素替换已使用的元素,因此您永远不会重复使用。
使用从该代码返回的结果作为索引来访问您的集合,将保证不选择重复项。