シャッフルではなくPRNGを使用してシャッフル範囲を生成する

StackOverflow https://stackoverflow.com/questions/464476

質問

任意のシード値が与えられた場合、線形時間および一定空間（出力が反復的に生成される場合）でシャッフル範囲[0..n）を生成できる既知のアルゴリズムはありますか？

nが大きいと仮定します。何百万もの場合、すべての可能な順列を潜在的に生成するための要件は、特にそれが実行不可能であるために必要ではありません（シード値スペースは巨大である必要があります）。これは、一定のスペースが必要な理由でもあります。 （つまり、範囲を長さnの配列に格納する必要があるため、配列シャッフルアルゴリズムは特に探していません。したがって、線形空間を使用します。）

質問162606 を認識していますが、認識していませんこの特定の質問への答えを提示してください-置換インデックスからその質問で与えられた置換へのマッピングは、巨大なシード値スペースを必要とします。

理想的には、期間と範囲がnの LCG のように動作します、ただし、LCGにaおよびcを選択する技術は微妙です。 <=>と<=>の制約を全期間で単純に満たすことでLCGは私の要件を満たすことができますが、もっと良いアイデアがあるかどうか疑問に思っています。

役に立ちましたか？

解決

Jasonの回答に基づいて、 C＃で簡単な単純な実装を作成しました。 Nより大きい次に大きい2のべき乗を見つけます。これは、cが比較的素数である必要があるため（2で割り切れないことを意味する）、aとcを生成するのは簡単です。 2で割り切れるには、（a-1）4で割り切れる必要があります。統計的には、次の数を生成するために1-2の一致が必要です（2N <！> gt; = M <！> gt; = 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();
    }
}

他のヒント

こちらは、 Linear Congruential Generator のPython実装です。 ：//stackoverflow.com/questions/464476/generated-shuffled-range-using-a-prng-rather-than-shuffling/#467767 "> FryGuyの回答。とにかくそれを書く必要があり、他の人に役立つかもしれないと思ったからです。

import random
import math

def lcg(start, stop):
    N = stop - start

    # M is the next largest power of 2
    M = int(math.pow(2, math.ceil(math.log(N+1, 2))))

    # c is any odd number between 0 and M
    c = random.randint(0, M/2 - 1) * 2 + 1

    # M=2^m, so make (a-1) divisible by all prime factors and 4
    a = random.randint(0, M/4 - 1) * 4 + 1

    first = random.randint(0, M - 1)
    x = first
    while True:
        x = (a * x + c) % M
        if x < N:
            yield start + x
        if x == first:
            break

if __name__ == "__main__":
    for x in lcg(100, 200):
        print x,

繰り返しのない0〜n-1のサイクルを生成することが保証されているアルゴリズムが必要なように聞こえます。要件に応じて、ほぼ間違いなくこれらのすべてがあります。 群論は、その背後にある理論を掘り下げたい場合、数学の最も有用な分野です。 。

高速で、予測可能性/セキュリティ/統計パターンを気にしない場合は、LCGがおそらく最も簡単なアプローチです。リンクしたウィキペディアのページには、この（かなり単純な）要件のセットが含まれています。

  

一般的なLCGの期間は最大で   m、およびはるかに少ないいくつかの選択肢   それより。 LCGにはフル   次の場合のみピリオド：

     
      
  1. cとmは比較的素数です。
    2.   
  2. a-1はmのすべての素因数で割り切れます
    3.   
  3. a-mが4の倍数の場合、1は4の倍数です
    4.   

別の方法として、期間N <！> gt; = nを選択することもできます。ここで、Nは便利な数値プロパティを持つ最小値で、nとN-1の間で生成された値はすべて破棄します。たとえば、最小のN = 2 k -1 <！> gt; = nを使用すると、線形フィードバックシフトレジスタ（LFSR）。または、お気に入りの暗号化アルゴリズム（RSA、AES、DESなど）を見つけて特定のキーを与え、それが並べ替える数字のスペースNを計算し、各ステップで1回暗号化を適用します。

nが小さいが、セキュリティを高くしたい場合、シーケンスSはnよりもはるかに高い周期Nを持っている可能性が高いので、おそらく最も難しいケースです。 Nより短い期間（たとえば、S mod nの出力を取得し、数字の非反復シーケンスを保証できる場合、攻撃者が使用する可能性のあるSに関する情報が得られます）

リニアフィードバックシフトレジスタを調べてください。これらを正確に使用できます。 それらを説明する簡単な方法は、種から始めて、式を使用して反復することです

x = (x << 1) | f(x)

f（x）は0または1のみを返すことができます

適切な関数fを選択すると、xは1から2 ^ n-1（nはある数）の間のすべての値を、適切な疑似ランダムな方法で循環します。 サンプル関数は、こちらで見つけることができます。 63個の値に使用できます

f(x) = ((x >> 6) & 1) ^ ((x >> 5) & 1)
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top