不明な長さのリンクリストの一様ランダム要素をどのように選択しますか？

1回のパスで不明な長さのリンクリストの一様ランダム要素を選択する方法、または2回でない場合はどうしますか？不明な長さのリンクリストの一様ランダム要素をどのように選択しますか？

2012-02-22 exlux15

私はあなたの質問にもう少し努力を払わなければならず、あなたが何を求めているのかを明確にしなければならないのではないかと心配しています。 –

ok。未知の長さのリンクされたリストの一様なランダム要素をどのように選ぶでしょうか？ – exlux15

これはあなたの質問です。興味深い質問です。それに応じてあなたの質問を編集してください私は –

リザーバサンプリングhttp://en.wikipedia.org/wiki/Reservoir_samplingを使用してください。データのパスは1回だけ必要です。

（すなわち、k番目の要素と既存の選択を置き換える）確率1/Kでそれを選ぶ、

後最初の要素（確率1）ピック：つの要素を取り出すため

これにより、要素の一様な選択が行われることが証明されます。

2012-02-22 19:46:16 ElKamina

私はそれを使用しようとしましたが、これはk個のランダム要素を選びます。しかし、私は最初の要素を選択する必要があります – exlux15

@AnilBabooram k = 1を使用しますか？とにかく、ポスト（wikiではない）で言及されたアルゴリズムは、1つの要素の場合です。 – ElKamina

リストをトラバースするために++の長さに沿ってwhileループを使用するといいです。 i = rand（）％lengthを使用すると、現在のノードでランダムに選択されますか？ – exlux15

答えて