有没有已知的算法可以在线性时间和常数空间内(迭代产生输出时),用任意种子值生成一个洗牌范围[0..n)?
假设n可能很大,例如数百万,因此不需要潜在地生成每个可能的排列,特别是因为这是不可行的(种子值空间需要巨大)。这也是常数空间要求的原因。(因此,我特别不寻找数组洗牌算法,因为它要求将范围存储在长度为n的数组中,因此会使用线性空间。)
我知道问题162606,但它没有回答这个特定的问题-该问题中给出的从排列索引到排列的映射将需要巨大的种子值空间。
理想情况下,它将像LCG一样具有周期和范围
假设n可能很大,例如数百万,因此不需要潜在地生成每个可能的排列,特别是因为这是不可行的(种子值空间需要巨大)。这也是常数空间要求的原因。(因此,我特别不寻找数组洗牌算法,因为它要求将范围存储在长度为n的数组中,因此会使用线性空间。)
我知道问题162606,但它没有回答这个特定的问题-该问题中给出的从排列索引到排列的映射将需要巨大的种子值空间。
理想情况下,它将像LCG一样具有周期和范围
n
,但是选择a
和c
的艺术很微妙。仅满足全周期LCG的a
和c
的约束可能满足我的要求,但我想知道是否有更好的想法。