sample collection without replacement

[Chris Landauer]

do you know in advance how many items you want?
do you know in advance how many items there are in the set?

there is a very nice algorithm if you want one uniformly selected item
from a subject set whose size you do not know in advance,
but which is contained in a set that can be traversed,
and with a known criterion for deciding whether an item of the containing
set is in the subject set -
it is used in many MUDs for uniform choices

set saved to nothing
loop current through containing set
        if (current is in my subject set)
                count++
                replace saved with current with probability 1/count

saved now has the selected item if count is nonzero

i imagine that this can be extended to multiple selections,
without replacement
(without replacement is probly easier than with replacement)

more real soon,
cal


Dr. Christopher Landauer
Advanced Programs Operations
National Systems Group
The Aerospace Corporation
The Hallmark Building, Suite 187
13873 Park Center Road, Herndon, Virginia 22071
e-mail: address@hidden
Phone: (703) 318-1666, FAX: (703) 318-5409