最後の結果と種子に基づいてランダムな整数を間隔から返す

Question

整数[a、b]の間隔があるとします。繰り返しずに、ランダムなメンバーを間隔内から返す関数を持ちたいと思います。間隔内のすべてのメンバーが探索されると、関数は同じ順序で、同じ最初のランダムシーケンスを同じ順序で戻し始めます。

例：A= 1、B= 5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

.

これは、AとBの間のすべての要素の配列をシャッフリングし、アレイが終了したら繰り返します。しかし、これはあまりにも多くのメモリスペースを取りますが、これは私の場合には適していません（私は何百万もの要素を持つかもしれません）。

代わりに、私がこのようにしたいと思う機能はこのようなものになるでしょう：

f(a, b, n, seed) -> n+1

.

ここで：

a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

.

トリックは、前に返される要素だけに基づいて繰り返しのない数を取得するための何らかの方法を知っています。最後に、初期化時にランダム化された循環リストのように動作しますが、メモリスペースを使用せずに動作します。

Answer 1

i範囲 $ [a、b] $ 、つまり放射線関数のランダムな置換を選ぶことをお勧めします。 $ \ PI：[a、b] \ x [a、b] $ 。次に、 $ i= a $ から始まる $ i $ を維持します。各ステップで、 $ \ pi（i）$ を増やしてから、 $ i $ を増やします。その $ b + 1 $ は $ a $ になります。

暗号化文献にこのようなランダムな置換を生成するための標準的な方法がある。フォーマットの保存暗号化を調べます。シードは暗号鍵です。 $ \ pi（i）$ $ o（1）$ 時間と$ \ を計算することができます。 $ o（1）$ スペース、これは非常に効率的で、多くのストレージの必要性を回避する必要があります。

次の出力が前の出力の関数になると主張する場合は、 $ g（i）= i + 1 $ にletできます。 SPAN CLASS="math-container"> $ g（b）= a $ ）、次に $ f（i）=pi ^ { - 1}（g （\ PI（I））$ 。ここで、 $ \ pi $ は、上記のように選択されたランダムな置換です。これにより、繰り返すランダムサイクルが表示されます。 $ [a、b] $ [a、b] $ の要素を介して。出力はシーケンス $ f（a）です。 、f（f（a））、f（f（f（a））、\ dots $ 。