アルゴリズム - 一様ランダム要素リンクリスト

Question

リンクリストから均一なランダム要素を取得するにはどうすればよいですか？リスト の長さを数え、あなたが数えているときに、ランダムな要素を生成します。リスト のランダム要素％の長さが0の場合は、その要素を選択します。

Answer 1

要素の選択を開始する前に、リストの長さが最初に必要です。したがって、平均1.5回の繰り返しが必要です。

最初はリストの長さを取得するためのものです。 [0 ... 1]の乱数にリストの長さを乗じて切り捨てます。 それはあなたが得なければならないインデックスです（あなたは別の繰り返しのために行く必要があります）。

int n = list.size() // Returns length of list 
int index = (int) (random_value() * n); // random_value returns a value between 0.0 and 1.0 
int* node = list.start() // goto start of list 
for (int iter = 0; 0 < n; n++) 
    node = node->next() // Goto next node 
return node