2

n各項目の倍数 (1 から ) が存在する可能性がある長さの一連の項目をランダム化するアルゴリズムを探していmます。追加の制約は、同じアイテムがk前のアイテムのアイテム内に表示されない可能性があることです。

が 100 をはるかに下回っていると仮定しnても、常に解が存在mしkます。役立つ場合は、入力を <item, frequency> ペアのリストに変更することもできます。

少し状況を説明するために、ゲームでミッションを生成していて、選択できる一連の目標があると仮定します。いくつかの目標は複数回出現する場合がありますが (例: 「ボスを倒す」)、互いに接近していてはならないため、単純に「バッグ」をシャッフルするのは良くありません。

リストをシャッフルし、アイテムの間隔を追跡しながら繰り返し、テストに失敗した場合は新しいシャッフルから開始できますが、コンパクトで実用的で、たとえば次のように簡単に実装できる、よりエレガントなソリューションを探していますC、C++、または JavaScript。言い換えれば、私が理解できない、または実装に苦労する可能性のある特別な言語機能や標準ライブラリ関数に依存するべきではありません。ただし、並べ替えやシャッフルなどの最も一般的なリスト操作は利用できると考えてよいでしょう。

4

1 に答える 1

1

有効な結果のセットに対して均一な確率が必要な場合は、あなたが提案した拒否スキーム (シャッフルして、配置が悪い場合は再起動する) が、正しくコーディングし、理解し、読み、維持するのが最も簡単になるだろうというのが私の予感です。ほとんどの順列が有効であるような数値であると仮定すると、おそらく最速にかなり近いでしょう。

ただし、貪欲に有効な値を選択し、自分自身をノックアウトしないことを期待することに基づいた、別の簡単なアプローチを次に示します。m無効な順列 (高いおよび)が多数ある場合、解決策が見つかる保証はまったくありませんk。

shuffled = list of length n
not_inserted = {0, 1, ..., n-1}
for each item i, frequency m_i, nearness constraint k_i:
    valid = not_inserted
    do m_i times:
        choose an index j from valid
        shuffled[j] = i
        not_inserted.remove(j)
        valid.remove(j-k_i, j-k_i+1, ..., j, ..., j+k_i)

が空の場合validは、構築した部分的なソリューションが悪いため、おそらく再起動する必要があります。小さい順にループすると失敗しにくくなると思いますm_i。

並べ替え/拒否のアプローチと比較して、このアプローチが失敗する頻度についてはわかりません（いくつかの数値に対して実装して実行することは興味深いでしょう...）。が適度に高い状況では高速になる可能性があると思いますkが、シャッフルは非常に高速であるため、通常は低速ですn << 100。

于 2012-07-27T08:45:52.223 に答える