本文介绍了使用 PRNG 而不是改组生成改组范围的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

是否有任何已知的算法可以在给定任意种子值的情况下,在线性时间和恒定空间(当输出迭代产生时)中生成混洗范围 [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 选择 ac 的艺术是微妙的.简单地在全周期 LCG 中满足 ac 的约束可能满足我的要求,但我想知道是否有更好的想法.

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 而不是改组生成改组范围的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

05-28 17:28
查看更多