问题描述
是否有任何已知的算法可以在给定任意种子值的情况下,在线性时间和恒定空间(当输出迭代产生时)中生成混洗范围 [0..n)?
Is there any known algorithm that can generate a shuffled range [0..n) in linear time and constant space (when output produced iteratively), given an arbitrary seed value?
假设 n 可能很大,例如数以百万计,因此不需要可能产生所有可能的排列,尤其是因为它不可行(种子值空间需要很大).这也是需要恒定空间的原因.(因此,我并不是在寻找数组改组算法,因为它要求范围存储在长度为 n 的数组中,因此会使用线性空间.)
Assume n may be large, e.g. in the many millions, so a requirement to potentially produce every possible permutation is not required, not least because it's infeasible (the seed value space would need to be huge). This is also the reason for a requirement of constant space. (So, I'm specifically not looking for an array-shuffling algorithm, as that requires that the range is stored in an array of length n, and so would use linear space.)
我知道问题 162606,但它没有给出这个特定问题的答案 - 从排列索引到该问题中给出的排列的映射需要巨大的种子值空间.
I'm aware of question 162606, but it doesn't present an answer to this particular question - the mappings from permutation indexes to permutations given in that question would require a huge seed value space.
理想情况下,它就像一个 LCG,周期和范围为 n
,但是为 LCG 选择 a
和 c
的艺术是微妙的.简单地在全周期 LCG 中满足 a
和 c
的约束可能满足我的要求,但我想知道是否有更好的想法.
Ideally, it would act like a LCG with a period and range of n
, but the art of selecting a
and c
for an LCG is subtle. Simply satisfying the constraints for a
and c
in a full period LCG may satisfy my requirements, but I am wondering if there are any better ideas out there.
推荐答案
基于 Jason 的回答,我在 C# 中做了一个简单直接的实现.找到下一个大于 N 的 2 的最大幂. 这使得生成 a 和 c 变得微不足道,因为 c 需要是素数(意味着它不能被 2 整除,也就是奇数),并且 (a-1) 需要可以被 2 整除,并且 (a-1) 需要被 4 整除.从统计上讲,生成下一个数字应该需要 1-2 个同余(因为 2N >= M >= N).
Based on Jason's answer, I've made a simple straightforward implementation in C#. Find the next largest power of two greater than N. This makes it trivial to generate a and c, since c needs to be relatively prime (meaning it can't be divisible by 2, aka odd), and (a-1) needs to be divisible by 2, and (a-1) needs to be divisible by 4. Statistically, it should take 1-2 congruences to generate the next number (since 2N >= M >= N).
class Program
{
IEnumerable<int> GenerateSequence(int N)
{
Random r = new Random();
int M = NextLargestPowerOfTwo(N);
int c = r.Next(M / 2) * 2 + 1; // make c any odd number between 0 and M
int a = r.Next(M / 4) * 4 + 1; // M = 2^m, so make (a-1) divisible by all prime factors, and 4
int start = r.Next(M);
int x = start;
do
{
x = (a * x + c) % M;
if (x < N)
yield return x;
} while (x != start);
}
int NextLargestPowerOfTwo(int n)
{
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return (n + 1);
}
static void Main(string[] args)
{
Program p = new Program();
foreach (int n in p.GenerateSequence(1000))
{
Console.WriteLine(n);
}
Console.ReadKey();
}
}
这篇关于使用 PRNG 而不是改组生成改组范围的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!