该问题给出了所有必要的数据:在给定区间[0,N-1]内生成一系列K个非重复整数的有效算法是什么.平凡算法(产生随机数,并把它们添加到序列,看着他们,看看他们是否已经在那里之前)是非常昂贵的,如果ķ大且足够接近ñ.
在从链表中有效地选择一组随机元素中提供的算法似乎比必要的更复杂,并且需要一些实现.我刚刚发现了另一种似乎可以完成工作的算法,只要您知道所有相关参数,只需一次通过即可.
我一直在阅读游戏编码完成(第4版),我在第3章的"Grab Bag of Useful Stuff"部分中理解"Set的伪随机遍历"路径时遇到了一些问题.
您有没有想过CD播放器上的"随机"按钮是如何工作的？它将随机播放CD上的每首歌曲,而不会播放两次相同的歌曲.这是一个非常有用的解决方案,可确保您的游戏中的玩家在有机会再次看到相同的内容之前,可以看到最广泛的功能,如对象,效果或角色.
在此描述之后,它继续讨论我尝试在Java中实现的C++实现,但是无法成功复制.它还简要描述了它是如何工作的,但我也没有得到它.
我发现这个 StackOverflow回答了一个类似的问题,但不幸的是,答案中的示例链接已经死了,我也不理解维基百科的文章,尽管关于它的内容的描述似乎描述了我正在寻找的内容.
要清楚,我不是在寻找一种随机重新订购集合的方法.我正在寻找一种方法,在重复之前从集合中选择一个元素.
有人可以解释这种行为是如何工作的并在Java中提供一个例子吗？谢谢!
[ 编辑 ]我认为在这里有一个实施的摘录来帮助解释我在说什么可能是有用的.
这是它的工作原理.通过选择三个大于零的随机值来计算跳过值.这些值成为二次系数,域值(x)设置为集合的序数值:
Skip = RandomA * (members * members) + (RandomB * members) + RandomC
使用此跳过值,您可以使用这段代码以伪随机顺序遍历整个集合一次:
nextMember += skip;
nextMember %= prime;
skip的值远大于您所设置的成员数,所选值似乎随机跳过.当然,此代码位于while循环内,以捕获所选值大于您的设置但仍小于素数的情况.