algorithm - （疑似）ランダムな順序で一連の数字を吐き出すアルゴリズムを探しています

Question

数列があるとします: {n, n+1, n+2, ... n + m}

事前に数値を保存せずに、シーケンス {1,2,3,...m} を指定すると、元のセットをランダム (または少なくとも疑似ランダム) の順序で吐き出す関数 f() を作成したいと考えています。 .

たとえば、シーケンスが {10, 11, 12, 13, 14, 15, 16, 17} であるとします。

   f(1) は 14 を返す可能性があります
   f(2) は 17 を返す可能性があります
   f(3) は 13 を返す可能性があります
   f(4) は 10 を返す可能性があります
   f(5) は 16 を返す可能性があります
   f(6) は 15 を返す可能性があります
   f(7) は 11 を返す可能性があります
   f(8) は 12 を返す可能性があります

過去のある時点で、同僚がこれを行うことができる数学的アルゴリズムを私に見せてくれましたが、それ以来、存在すること以外はほとんどすべてを忘れてしまいました. 事前にシーケンスを取得し、関数で使用されるシーケンスからいくつかの定数を生成する必要があったことを覚えています。そして、不思議に思っている人のために、悲しいことに、私はその同僚との連絡を失いました.

この質問の答えは私が望むものに近いように見えますが、答えによって出力を特定のシーケンスに事前に制限できるかどうかはわかりません。

---

編集：

もう少し明確にするために、元のシーケンスまたはシャッフルされたシーケンスを保存したくありません。元のシーケンスから関数 f() を生成したい。

イライラするのは、私がこれを見たということです.Googleでもう一度見つけるのに十分な記憶がありません.

Fisher-Yates アルゴリズムは、デッキの並べ替えやシャッフルには最適ですが、私が探しているものではありません。

Answer 1

この質問は、[n、...、n + m]の番号が付けられた（m + 1）枚のカードのデッキをシャッフルすることに似ています。番号付け（したがってn）は重要ではないことに注意してください。重要なのは、カードを区別できることです。n（必要に応じて、後で簡単にバックを追加できます。）

やりたいことをするために、フィッシャー-イェーツシャッフルを実行し、これまでにシャッフルするために選択されたインデックスを追跡することができます。これにより、要求に応じて、値自体の別のコピーを保存することを回避できます。

Answer 2

元のシーケンスをすべて元に戻したいように聞こえるので、質問は少し混乱しますが、4 と 8 の両方が 10 にマッピングされ、12 には何もマッピングされません。

実際に 1:1 のマッピングを意味する場合、探しているのは元のセットのランダムな順列です。最初にセットを収集するかどうかにかかわらず、これを行う方法があります (ただし、それを生成する何かが必要になるか、自分がどこにいるかを追跡する必要があります)。

また、n は重要ではないことに注意してください。いつでも 0,1,2,...m を使用でき、必要に応じてすべてに n を追加できます。

私がこれを正しく解釈し、実際にシャッフル アルゴリズム (つまり、カードのデッキをシャッフルするのと同じようにシャッフルと呼ばれるランダム順列) を探していると仮定すると、Fisher-Yatesを見てください。

[編集] あなたの更新に基づいて、あなたが直面する問題は次のとおりです: 順列を明示的にエンコードしたくないが、f を構築するために何らかの方法でエンコードする必要があります。最も簡単な方法は、並べ替えられたインデックスを実際に配列に格納することですが、何らかの理由 (大きすぎるなど) で格納したくない場合は、さまざまな方法でエンコードできます。ただし、これがどれほど単純であるかには情報理論上の限界があるため、無料のランチはありません。とにかく、「エンコーディング順列」に関する作業を調べることからいくつかのアイデアを得ることができます。たとえば、この論文のようなものです

Answer 3

入力は、、f(x) => x + 9またはより一般的には1から始まるf(x) => n - 1 + xものとして記述されます。x

xをシャッフルされた値にマップする関数を説明する別の質問にリンクします。r(x)0 <= r(x) <= m

そうf(r(x) + 1)か(r(x) + n)、あなたが望む価値をあなたに与えるべきです。

小さいm場合は、トレイルとエラーによって標準の乱数ジェネレーターのシードを見つけることもできるはずです。独自のジェネレーターをコーディングしたくない場合は、m+1modを実行すると異なる値が生成されます。m+1

Answer 4

リストに初期値を追加します。
次に、乱数を使用して、リストの現在のサイズの範囲内の新しいインデックス値を選択します。
そのインデックスを使用して番号を選択し、リストから削除します。

誰かがすでに指摘しているように、これはカードのデッキを持っていて、一度に1枚のカードをランダムに取り除くことに似ています。

Answer 5

元の関数の結果をどこかに保存せずに値を返すことはできません。理由:

乱数ジェネレーターは、元のシーケンスから次の値を返すように指示します: 5 番目、11 番目、3 番目。

最初の 4 つの値をスキップし、5 番目を返し、別の 5 をスキップし、11 番目を返します...どこかに保存せずに 3 番目を返すにはどうすればよいでしょうか?

あなたが逃げることができる最も近いことは、リストを作成し、スキップしたすべての値を追加することですが、それは非常に厄介で、おそらく努力する価値はありません. また、シャッフル アルゴリズムが非常に大きな値を返し、次に非常に小さな値を返す場合は、非常に遅くなります (この場合、最初にほとんどの値を効果的にリストにコピーしますが、これは避けたいことです)。

私は自分のケースを休ませます。

Answer 6

選択したシーケンスに多項式を当てはめることができます。それがあなたの同僚があなたに示したものだと思います。ただし、順列を覚えるだけに比べてスペースは節約されません。

Answer 7

これは、私が独自に作成した言語の疑似コードです。

function f(array a)
    array newArray
    while a.size() == 0
        int position = randomNumber(1 to a.size())
        int removedNumber = a[position]
        a.remove(position)
        newArray.insertAtEnd(removedNumber)
    end while
    return newArray

Answer 8

1:1 マッピングが必要な場合は、他の回答で述べたように、Fisher-Yates を使用してください。

1:1 マッピングを気にせず、結果のすべての値が指定されたシーケンスからのものである必要がある場合 (繰り返しの可能性あり)、指定された範囲でランダム関数を使用できます。

たとえば、C++ では、次のように rand() を使用できます。

result = rand() % (m+1) + n

あなたの例では、

result = rand() % 8 + 10

10 から 17 の間の整数を生成します。