Subj : Re: Random Subset of Linked List
To   : comp.programming
From : Chris Dollin
Date : Tue Sep 13 2005 04:58 pm

MSCHAEF.COM wrote:

> 
> I have a question that seems like it might be appropriate for this group:
> Given a linked list, I'm trying to pick a random subset with a specific
> number of items. The constraint is that all elements in the original list
> have the same chance of ending up in the final subset.

Generate the array of values 1..N of indexes into the list. 

Shuffle.

Pick the list elements with indexes in the first K elements of
the shuffled array (sort that section).

Shuffle is easy but (a) slightly non-trivial and (b) seriously
non-trivial.

(a) is just a matter of coding the algorithm right.

(b) is an issue of picking a good way of reducing the output from
    your local random-number generator to an integer in the range
    1..Whatever *without bias*.

-- 
Chris "electric hedgehog" Dollin
Logic is rational /re/construction. Life is construction.

.