この質問と多かれ少なかれ同じですが、選択するコンテナーが可能な限り一般的 (つまり、Forward Containerのみ、または単に単純なContainer ) である場合、コンテナーに .size() があると想定されるべきではありません。 2 回 (サイズをカウントするために 1 回、結果セットを取得するために 2 回) 歩くことは受け入れられません。
私は、もう少し複雑で、必要以上の依存関係を持つ1つのソリューションを持っているので、3〜5行の範囲で何かを望んでいます。
1 に答える
2
「ランダム要素」とは、要素が均等に分散されていることを意味すると思います。
シーケンスの長さがわからず、事前に計算することもできないため、ランダムなシーケンスを徐々に構築する必要があります。それでは、それを実行してみましょう。使用する確率がすべてうまく加算され、最初に望んでいた結果が得られることを願っています。
これは 2 つの手順で行います。まず、どのシーケンス番号を描画するかを決定します。次に、必要に応じてランダムな順序を選択できます (質問からは明確ではありませんでした)。そして、私はあなたの N 'K' と呼びます。
最初に、K 個の描画要素を保持するために、K 個の要素配列を作成します。シーケンスの最初の K 個の要素を調べて、それらを配列にコピーします。シーケンスに K 個の要素がない場合、「No can do」と言います。
これで、K サイズのシーケンスから K 個のランダムな要素があることがわかりました。シーケンスの最後にいる場合は、完了です。そうでない場合は、K+1 サイズのシーケンスがあることがわかります。ここには 2 つのオプションがあります。K+1 番目の項目を選択するか、選択しないかです。
K+1番目のアイテムが選ばれる確率は? K+1 番目のアイテムが選択されない確率を計算する方が簡単だと思います。K+1 から K 個の要素を選択するには (K+1 対 K) の方法があり、K+1 の要素が表示されない場合に K の要素を選択するには (K 対 K) 通りの方法しかありません。したがって、(K オーバー K) / (K+1 オーバー K) は、K+1 番目の項目が選択されない確率です。
したがって、0 から 1 の間の乱数を選択します。1/(K+1) 未満の場合、K+1 番目の要素はシーケンスに表示されません。乱数がそれより大きい場合、K+1 番目の要素がシーケンスに表示されます。1 から K までのランダムな要素を選択し、K+1 番目の要素に置き換えます。
次のアイテム、K+2 番目のアイテムに移動します。そしてまた同じことをします。K+2 番目の項目がシーケンスに表示されない確率は、(K に対する K+1) / (K に対する K+2) です。
シーケンスが使い果たされるまでそれを行います。次に、シーケンスからランダムに選択された K 個の要素のリストがあります。
それらはランダムに並べられていないことに注意してください（少なくとも短いシーケンスではそうではありません）。そのため、ランダムな K サイズの順列を選択することをお勧めします。
免責事項: 確率は問題です。これは私には正しいように思えますが、何かを見逃して最終結果が均等に分配されない可能性があります。他の人はすぐに教えてくれます。
于 2013-07-07T07:15:23.497 に答える