该问题给出了所有必要的数据:在给定区间[0,N-1]内生成一系列K个非重复整数的有效算法是什么.平凡算法(产生随机数,并把它们添加到序列,看着他们,看看他们是否已经在那里之前)是非常昂贵的,如果ķ大且足够接近ñ.
在从链表中有效地选择一组随机元素中提供的算法似乎比必要的更复杂,并且需要一些实现.我刚刚发现了另一种似乎可以完成工作的算法,只要您知道所有相关参数,只需一次通过即可.
在给定任意种子值的情况下,是否有任何已知的算法可以在线性时间和常数空间(当迭代生成输出时)生成混洗范围[0..n]？
假设n可能很大,例如数百万,因此不需要潜在地产生每种可能的排列,尤其是因为它是不可行的(种子值空间需要很大).这也是需要恒定空间的原因.(所以,我特别不是在寻找一种阵列混洗算法,因为这需要将范围存储在长度为n的数组中,因此会使用线性空间.)
我知道问题162606,但它没有给出这个特定问题的答案 - 从排列索引到该问题中给出的排列的映射需要巨大的种子值空间.
理想情况下,它的行为类似于具有周期和范围的LCGn,但选择a和c制作LCG 的艺术是微妙的.只要满足约束a,并c在一个完整周期LCG可满足我的要求,但如果有更好的想法在那里我想知道.