我想生成0到1000之间永远不会重复的唯一随机数(即6不会出现两次),但这并不是像以前的值的O(N)搜索那样.这可能吗？
说我有y不同的值,我想x随机选择它们.这样做的有效算法是什么？我可以打电话给rand() x时间,但如果很大x,表现会很差y.
请注意,此处需要组合:每个值应具有相同的概率,但结果中的顺序并不重要.当然,任何生成排列的算法都是合格的,但我想知道如果没有随机顺序要求,是否可以更有效地做到这一点.
如何有效地生成0和上限N之间的K个非重复整数的列表,涵盖了这种情况的排列.
该问题给出了所有必要的数据:在给定区间[0,N-1]内生成一系列K个非重复整数的有效算法是什么.平凡算法(产生随机数,并把它们添加到序列,看着他们,看看他们是否已经在那里之前)是非常昂贵的,如果ķ大且足够接近ñ.
在从链表中有效地选择一组随机元素中提供的算法似乎比必要的更复杂,并且需要一些实现.我刚刚发现了另一种似乎可以完成工作的算法,只要您知道所有相关参数,只需一次通过即可.
刚看了一个关于生成100个随机整数的排序列表的代码高尔夫问题.然而,突然出现的是,您可以生成一个正增量列表,并将它们添加到运行总计中,这样:
deltas: 1 3 2 7 2
ints: 1 4 6 13 15
实际上,你会使用浮点数,然后标准化以适应某些上限,并且圆形,但效果是相同的.
虽然它不会产生更短的代码,但如果没有排序步骤肯定会更快.但我没有真正处理的事情是这样的:整数分布是否与从均匀分布的概率密度函数生成100个随机整数相同？
编辑:示例脚本:
import random,sys
running = 0
max = 1000
deltas = [random.random() for i in range(0,11)]
floats = []
for d in deltas:
running += d
floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)
谁的输出(公平骰子滚动)是:
[24, 71, 133, 261, 308, 347, 499, 543, 722, 852]
更新: Alok的回答和Dan Dyer的评论指出,使用指数分布进行增量可以得到均匀的整数分布.