5

完全な質問は次のとおりです。

サイズの配列からm個の整数のセットをランダムに生成するメソッドを記述しますn。各要素は、選択される確率が等しい必要があります`

この質問は「コーディングインタビューのクラック」から選択され、解決策は次のとおりです。

要素を配列の先頭にある要素と交換してから、配列に含まれるのは要素j以上であることを「覚えておく」ことができます。つまり、を選択subset[0]すると、配列の最初の要素にarray[k]置き換えられます。array[k]を選択するsubset[1]と、「デッド」と見なされ、1と配列の間array[0]のランダムな要素が選択されます。次に、subset [1]を、に設定し、 array[1]に等しく設定します。要素0と1は「デッド」になりました。から、などから選択されるようになりました。ysize()array[y]array[y]Subset[2]array[2]array[array size()]

私の質問は、乱数を選択する配列を縮小する場合、各番号が選択される確率です1/remaining_num_elements。すべての要素でどのように平等に保たれますか？

4

3 に答える 3

4

m数字の袋から乱数を選んでいるように考えてください。n最初のj要素はを表しthe numbers in your hand、残りの要素はを表しthe numbers still in the bagます。（あなたの本が示唆しているように、あなたjは0から数字を引き出すために繰り返します。そして、あなたがすでにバッグから引き出した整数の数を表します。）m - 1j

実生活でバッグから整数を選択する場合m、新しい数値を選択するたびに、手からではなくバッグからのみ取得します。したがって、remaining_num_elements各ステップで縮小します。

このように考えるとき、この方法が各要素が選択される確率が等しいことを保証することを理解するのは簡単なはずです。

于 2012-12-07T01:20:42.823 に答える
4

乱数を選択する配列を縮小する場合、各番号が選択される確率は1/remaining_num_elementsです。

はい、あなたは正しいですが、特定のターンに要素が拾われる1/remaining_num_elements確率です。ここでは、要素が最終的に順番にピックアップされる確率に関心があります。これはすべての要素で同じままです。mn

あなたが尋ねる必要がある質問は次のとおりです：各n要素は順番に拾われるという公平で平等なチャンスを得ますか？m答えはイエスです。なぜなら、

P（要素は最終的に要素のセットでピックアップされmます）= P（要素は1番目のターンでピックアップされます）+
P（要素は1番目のターンでピックアップされません）* P（要素は2番目のターンでピックアップされます）+
P（最初の2ターンで要素がピックアップされない）* P（3番目のターンで要素がピックアップされる）+...など

nこれは、計算すると、最初に存在するすべての要素で同じままです。

于 2012-12-07T12:19:11.550 に答える
0

確率に見られる違いは、それが条件付きプロパティであるという事実によるものです（何かがすでに選択されており、最後のフェッチでこの要素が選択またはフェッチされていないという事実）。ただし、確率を超えて、または特定のボールを全体的に選択するための同等の公平性は変わりません。

于 2016-09-03T04:47:04.867 に答える