生成利用PRNG洗牌的范围，而不是洗牌 [英] Generating shuffled range using a PRNG rather than shuffling

问题描述

是否有任何已知的算法，可产生线性时间和恒定空间（输出时产生的迭代），一个拖着范围[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 ，但它不present回答此问题的讨论 - 映射关系置换指标在该问题将需要大量的种子值空间给排列

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 ，但选择 A 和 C 为LCG的艺术是微妙的。只要满足约束 A 和 C 在一个完整周期LCG可满足我的要求，但如果我想知道有有什么更好的想法在那里。

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.

推荐答案

根据<一href="http://stackoverflow.com/questions/464476/generating-shuffled-range-using-a-prng-rather-than-shuffling#465473">Jason's回答，我做了在C＃中的简单直接的实现。发现2的下一个最大的功率大于N.这使得有微不足道的生成a和c，由于C必须是互质（意指由2不能整除，又名单数），和（a-1）的需要要能被2整除，和（A-1）必须要能被4整除据统计，它应该需要1-2同余生成一个号码（因为2 N> = 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洗牌的范围，而不是洗牌的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！