14

という名前のリストがありelements、それぞれがブール値のプロパティ を満たしているか満たしていないとしますp。p一様分布でランダムに満たす要素を1つ選びたい。このプロパティを満たす項目がいくつあるかは事前にわかりませんp。

次のコードはこれを行いますか?:

pickRandElement(elements, p)
     randElement = null
     count = 0
     foreach element in elements
          if (p(element))
               count = count + 1
               if (randInt(count) == 0)
                    randElement = element

     return randElement

(randInt(n)でランダムな intkを返します0 <= k < n。)

4

5 に答える 5

14

それは数学的に機能します。帰納法で証明できます。

pを満たすn = 1要素に対して明らかに機能します。

n+1 要素の場合、確率 1/(n+1) の要素 n+1 を選択するので、その確率は OK です。しかし、それは前の n 個の要素の 1 つを選択する最終確率にどのように影響するのでしょうか?

要素 n+1 が見つかるまで、前の n のそれぞれが確率 1/n で選択される可能性がありました。ここで、n+1 を見つけた後、要素 n+1 が選択される可能性は 1/(n+1) であるため、以前に選択された要素が選択されたままになる可能性は /(n+1) です。これは、n+1 個の検索後に選択される最終的な確率が 1/n * (n/n+1) = 1/n+1 であることを意味します。これは、均一な分布のためにすべての n+1 要素に必要な確率です。

n = 1 で機能し、与えられた n+1 で機能する場合、すべての n で機能します。

于 2009-06-08T18:38:18.410 に答える
3

プログラミングの実践では、ページ。70、（マルコフ連鎖アルゴリズム）そのための同様のアルゴリズムがあります：

[...]
  nmatch = 0;
  for ( /* iterate list */ )
    if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
      w = suf->word;
[...]

「項目がいくつあるか分からない場合に、ランダムに 1 つの項目を選択するアルゴリズムに注意してください。変数 nmatch は、リストがスキャンされるときに一致する数をカウントします。式は

rand() % ++nmatch == 0

nmatch をインクリメントし、確率 1/nmatch で true になります。」

于 2009-06-08T18:13:56.317 に答える
1

decowboy は、これがTopCoderで機能することを証明しています。

于 2009-06-08T19:13:52.257 に答える
0

明確にするために、私は試してみます：

pickRandElement(elements, p)
     OrderedCollection coll = new OrderedCollection
     foreach element in elements
          if (p(element))
               coll.add(element)
     if (coll.size == 0) return null
     else return coll.get(randInt(coll.size))

私にとって、それはあなたがやろうとしていることをより明確にし、自己文書化しています. その上、よりシンプルでエレガントになり、それぞれが均等な分布で選択されることが明らかになりました。

于 2009-06-08T18:12:22.357 に答える