25

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

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

私は質問 162606を認識していますが、この特定の質問に対する回答は提示されていません。その質問で指定された順列インデックスから順列へのマッピングには、巨大なシード値スペースが必要になります。

理想的には、周期と範囲がのLCGのように機能しますが、 LCGnを選択する技術は微妙です。LCG の全期間の制約を満たすだけで、私の要件を満たすことができるかもしれませんが、他にもっと良いアイデアがあるかどうか疑問に思っています。acac

4

5 に答える 5

8

Jason の回答に基づいて、C# で単純でわかりやすい実装を作成しました。N よりも大きい次の 2 のべき乗を見つけます。これにより、a と c を生成するのは簡単になります。 (a-1) は 2 で割り切れる必要があり、(a-1) は 4 で割り切れる必要があります。統計的には、次の数を生成するには 1 ～ 2 回の合同が必要です (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();
    }
}
于 2009-01-22T01:32:59.430 に答える
5

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

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

一般的な LCG の周期は最大で m であり、一部の選択肢ではそれよりもはるかに短いです。次の場合に限り、LCG は全期間を持ちます。

  1. c と m は互いに素であり、
  2. a - 1 は m のすべての素因数で割り切れます
  3. m が 4 の倍数の場合、a - 1 は 4 の倍数

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

n が小さいが、セキュリティを高くしたい場合、おそらく最もトリッキーなケースです。これは、任意のシーケンス S の周期 N が n よりもはるかに長い可能性が高いためですが、周期が短い非反復数シーケンスを導出することも自明ではありません。 N よりも (たとえば、S mod n の出力を取得し、数値の非反復シーケンスを保証できる場合、攻撃者が使用する可能性のある S に関する情報が得られます)

于 2009-01-21T14:14:05.853 に答える
3

それを行う 1 つの方法については、ブロック暗号による安全な順列に関する私の記事を参照してください。

于 2009-01-23T19:33:35.987 に答える
1

Linear Feedback Shift Registers を調べてください。まさにこれに使用できます。それらを説明する簡単な方法は、シードから始めて、式を使用して反復することです

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)
于 2009-02-05T12:42:19.523 に答える