The algorithm is as follows:

`Element choice;`

int count = 0;

for (Element e = head; e != NULL; e = e->next) {

if (rand01() <= (1.0 / ++count)) {

choice = e;

}

}

You can easily show that when this finishes, *choice* is equal to any given element with probability 1/*n*, where *n* is the number of elements: The probability of setting the *i*^{th} element to be the new choice is 1/*i*. The probability of *not* selecting any of the subsequent elements to be the new choice is the product as *j* goes from *i*+1 to *n* of (1 - 1/*j*), which if you work out the math ends up as *i*/*n*. Multiply the two probabilities together and you get 1/*n.*

Labels: algorithms, programming