25

固定空間で1..Nという数字のランダム順列を列挙しようとしています。これは、すべての番号をリストに保存できないことを意味します。その理由は、Nが非常に大きく、使用可能なメモリよりも多くなる可能性があるためです。私はまだ、そのような番号の順列を一度に1つずつ歩き、各番号を1回だけ訪問できるようにしたいと思っています。

これは特定のNに対して実行できることを私は知っています。多くの乱数ジェネレーターは、状態空間全体をランダムに循環しますが、完全に循環します。状態サイズが32ビットの優れた乱数ジェネレーターは、数値0 ..（2 ^ 32）-1の順列を出力します。すべての番号は1回だけです。

たとえば、Nを任意の数に選択し、2の累乗に制限されないようにしたい。このためのアルゴリズムはありますか？

4

6 に答える 6

11

最も簡単な方法は、おそらく、気になるよりも広い範囲のフルレンジPRNGを作成することです。それが必要以上の数を生成する場合は、それを破棄して次のPRNGを取得します。

同じもののほとんどのバリエーションである別の可能性は、線形フィードバックシフトレジスタ（LFSR）を使用して最初に数値を生成することです。これにはいくつかの利点があります。まず、LFSRはおそらくほとんどのPRNGよりも少し高速です。第二に、（私は）あなたが望む範囲に近い数を生成するLFSRを設計するのは少し簡単ですが、それでも繰り返しなしで（疑似）ランダムな順序でその範囲の数を循環することを確認してください。

詳細に多くの時間を費やすことなく、LFSRの背後にある数学は非常に徹底的に研究されてきました。繰り返しなしでその範囲内のすべての数値を実行するものを作成するには、既約多項式に対応する「タップ」のセットを選択するだけです。自分でそれを検索したくない場合は、ほぼすべての妥当なサイズの既知のテーブルを見つけるのは非常に簡単です（たとえば、簡単に見てみると、ウィキペディアの記事には最大19ビットのサイズのテーブルがリストされています）。

メモリが機能する場合、これまでに可能なビットサイズの既約多項式が少なくとも1つあります。これは、最悪の場合、必要な範囲の約2倍のジェネレーターを作成できるため、平均して、生成する1つおきの数値を（ほぼ）破棄することになります。LFSRの速度を考えると、それを実行しても、かなり許容できる速度を維持できると思います。

于 2012-04-07T13:49:31.400 に答える
10

それを行う1つの方法は

  1. pより大きいN、できればそれほど大きくない素数を見つけます。
  2. gモジュロ単位の原始根、つまり、がの倍数である場合に限り、そのようなp数を見つけます。1 < g < pg^k ≡ 1 (mod p)kp-1
  3. 。より大きい値を無視して、を実行g^k (mod p)します。k = 1, 2, ...N

すべての素数pには、 1φ(p-1)の原始根があるため、機能します。ただし、見つけるのに時間がかかる場合があります。一般的に、適切な素数を見つけるのははるかに簡単です。

原始根を見つけるために、私は試行錯誤よりも実質的に良いことは何も知りませんが、素数をp適切に選択することによって、迅速な発見の確率を高めることができます。

原始根の数はであるため、1からの範囲でφ(p-1)ランダムに選択した場合、原始根が見つかるまでの予想試行回数はです。したがって、比較的大きくなるように選択する必要があります。つまり、明確な素数が少ない必要があります。除数（そして、因子2を除いて、できれば大きなものだけ）。rp-1(p-1)/φ(p-1)pφ(p-1)p-1

ランダムに選択する代わりに2, 3, 5, 6, 7, 10, ...、原始根であるかどうかを順番に試すこともできます。もちろん、完全な累乗をスキップします（または、一般にすぐに削除されます）。これは、必要な試行回数に大きく影響しないはずです。

xつまり、数値が原始根モジュロであるかどうかをチェックすることになりpます。p-1 = q^a * r^b * s^c * ...明確な素数を持つ場合q, r, s, ...、xは原始根であり、

x^((p-1)/q) % p != 1
x^((p-1)/r) % p != 1
x^((p-1)/s) % p != 1
...

したがって、適切なべき乗剰余が必要です（2乗を繰り返すことによるべき乗は、そのために役立ち、各ステップのモジュラスによって減少します）。そして、の素因数分解を見つけるための良い方法p-1。ただし、単純な試行割り算でさえO（√p）であり、順列の生成はΘ（p）であるため、因数分解が最適であることが最優先事項ではないことに注意してください。

于 2012-04-07T13:42:34.973 に答える
4

これを行う別の方法は、ブロック暗号を使用することです。詳細については、このブログ投稿を参照してください。

ブログの投稿には、多数のソリューションが含まれている「任意の有限ドメインを持つ暗号」という論文へのリンクがあります。

于 2012-04-11T05:32:11.310 に答える
3

プライム3を考えてみましょう。考えられるすべての出力を完全に表現するには、次のように考えてください。

bias + step mod prime

これbiasは単なるオフセットバイアスです。stepはアキュムレータであり（1たとえば、0, 1, 2シーケンスになっているだけで、2結果は0, 2, 4）になりprime、順列を生成する素数です。

例えば。の単純なシーケンスは0, 1, 2...

0 + 0 mod 3 = 0
0 + 1 mod 3 = 1
0 + 2 mod 3 = 2

これらの変数のいくつかを1秒間変更して、（説明のためbiasに）1とを取ります...step2

1 + 2 mod 3 = 0
1 + 4 mod 3 = 2
1 + 6 mod 3 = 1

まったく異なるシーケンスを作成したことに気付くでしょう。セット内の数字は繰り返されず、すべての数字が表されます（全単射です）。オフセットとバイアスのそれぞれの固有の組み合わせはprime! 、セットの可能な順列の1つになります。の場合、さまざまな可能なパーミュレーションがあることがprimeわかります。36

0,1,2
0,2,1
1,0,2
1,2,0
2,0,1
2,1,0

上記の変数で計算を行うと、同じ情報要件が発生することはありません...

1/3! = 1/6 = 1.66..

...対..。

1/3 (bias) * 1/2 (step) => 1/6 = 1.66..

制限は単純で、bias範囲内である必要があり、範囲内0..P-1でstepある必要があります1..P-1（私は機能的に、自分の仕事で算術を使用0..P-2および追加しているだけです）。1それ以外は、どんなに大きくてもすべての素数で動作し、2、3の整数を超えるメモリを必要とせずにそれらのすべての可能な一意のセットを並べ替えます（それぞれが技術的に素数自体よりわずかに少ないビットを必要とします）。

このジェネレーターは、素数ではないセットを生成するために使用されることを意図していないことに注意してください。そうすることは完全に可能ですが、タイミング攻撃を引き起こす可能性があるため、セキュリティに敏感な目的にはお勧めしません。

とはいえ、この方法を使用して素数ではないセットシーケンスを生成する場合は、2つの選択肢があります。

まず（そして最も単純で最も安い）、探している設定サイズよりも少し大きい素数を選び、ジェネレーターに属していないものを単に破棄させます。繰り返しになりますが、これがセキュリティに敏感なアプリケーションである場合、これは非常に悪い考えです。

次に（はるかに複雑でコストがかかる）、すべての数値が素数で構成されていることを認識し、複数のジェネレーターを作成して、セット内の各要素の積を生成します。言い換えると、nofに6は、一致する可能性のあるすべてのプライムジェネレーター6（この場合は2、3）が含まれ、順番に乗算されます。これは高価であるだけでなく（数学的にはよりエレガントですが）、タイミング攻撃を導入するため、あまりお勧めできません。

bias最後に、およびまたは...のジェネレータが必要な場合stepは、同じファミリの別のジェネレータを使用してみませんか:)。突然、真の単純ランダムサンプルの作成に非常に近づきました（これは通常は簡単ではありません）。

于 2017-03-26T03:28:55.607 に答える
2

x=(x*m+c)%bここでは、LCG（スタイルジェネレーター）の根本的な弱点が役立ちます。

ジェネレータが適切に形成されている場合は、（の係数の場合に提供される）x%fよりも低いすべての値の繰り返しシーケンスでもあります。ffb

通常は2の累乗であるためb、これは、32ビットジェネレーターを使用して、上位ビットをマスクすることでnビットジェネレーターに減らすことができ、同じフルレンジプロパティを持つことを意味します。

これは、適切なマスクを選択することにより、破棄値の数をN未満に減らすことができることを意味します。

残念ながら、LCGは、上記とまったく同じ理由で不十分なジェネレータです。

また、これには、@JerryCoffinの回答に対するコメントで指摘したのとまったく同じ弱点があります。それは常に同じシーケンスを生成し、シードが制御するのはそのシーケンスのどこから開始するかだけです。

于 2017-09-15T17:23:12.073 に答える
0

DanielFischerが提案した方法でランダム置換を生成するSageMathコードを次に示します。

def random_safe_prime(lbound):
    while True:
        q = random_prime(lbound, lbound=lbound // 2)
        p = 2 * q + 1
        if is_prime(p):
            return p, q


def random_permutation(n):
    p, q = random_safe_prime(n + 2)

    while True:
        r = randint(2, p - 1)
        if pow(r, 2, p) != 1 and pow(r, q, p) != 1:
            i = 1
            while True:
                x = pow(r, i, p)
                if x == 1:
                    return

                if 0 <= x - 2 < n:
                    yield x - 2

                i += 1
于 2018-03-09T13:18:27.877 に答える