0

すべてのオブジェクトが検査されるまで、一度に1つずつ検査したいオブジェクトのコレクションがあります。各オブジェクトは、多くの重複の可能性がある事前定義された重みによって選択されます。最終結果は、コレクションからのアイテムの順序付きリストになります。このリストを取得するための効率的な方法は何ですか？

たとえば、指定されたボリュームを持つ次のボールについて考えてみます。

A: 2
B: 3
C: 25
D: 100

バッグにAボール4個、Bボール3個、Cボール1個、Dボール2個を入れてみましょう。特定のボールを引く確率がその体積に比例すると仮定すると、この時点で特定のDボールを引く確率は100/242です（同じ重量ですが同じではありません）。このDが描画されたとし、続行します。Dボールが以前に取り外されたため、この時点でCを引く確率は25/142です。ここでCボールを引いて続行するとします。DCDBABBAのようなシーケンスになるように、すべてのボールが削除されるまで描画を続けます。

4

1 に答える 1

1

[編集：個々のボール番号を追加するために更新]

さまざまな種類nのボールがあるとします。初期状態を表すトリプルの要素配列をk作成します。これを行うときは、それぞれをに追加します。これは0から始まります。k(balltype, weight, count)weight[i] * count[i]total

まず、ボールの種類ごとにボール番号の配列を設定します。

  1. 1iからk：
    • 1 <= j <=に割り当てて、count[i]要素配列を作成します。b[i]jb[i][j]count[i]

次に、ランダムにボールを選びます。次の手順を何n度も繰り返して、ランダムな順序ですべてのボールを選択できます。

  1. r0から-1までのランダムな整数を選択してtotalください。
  2. p=0に設定します。
  3. 1iからk：
    • に追加weight[i] * count[i]しpます。
    • 場合r < p：
      • タイプのボールを選びましたballtype[i]。出力します。
      • c1からを含むランダムな整数を選択してcount[i]ください。
      • b[i][c]ボール番号として出力します。
      • 1ずつ減らしcount[i]ます。
      • セットb[i][c] = b[i][count[i]]。これにより、未使用のボール番号が「密」に保たれます。
      • セットtotal = total - weight[i]。
      • 止まる。

すべてのボールを選ぶnにはO（nk）時間がかかります。これは、トリプルの配列の最後のエントリを0に達するiたびに（つまり、タイプのすべてのボールが使い果たされたときに）位置に移動し、1ずつ減らすことで、約2倍高速化できます。ただし、ボールを選択するコードの場合は作業を継続するには、配列全体もにコピーするか、別の間接層を使用する必要があります。count[i]inb[n]b[i]

于 2012-12-18T21:51:46.937 に答える