collections/constrained_subset_utils library
Weighted random subset selection without replacement — roadmap #476.
Picks up to count distinct items from a list where each item's chance of
selection is proportional to its weight, with no item chosen twice, and with
arbitrary items excluded outright. Naive weighted sampling without
replacement is awkward (re-normalizing after each draw is O(n) per pick);
this uses the Efraimidis-Spirakis one-pass reservoir trick: give each
eligible item a key random^(1/weight) and keep the count items with the
largest keys. A higher weight pushes the key toward 1, so heavier items win
more often — and a single pass yields a correct weighted sample.
Randomness is injectable via Random so callers can seed it for deterministic, testable selection.