weightedSubset<T> function

List<T> weightedSubset<T>(
  1. List<T> items, {
  2. required int count,
  3. required double weight(
    1. T
    ),
  4. Set<T> exclude = const <Never>{},
  5. Random? random,
})

Selects up to count distinct items from items, weighted by weight, without replacement.

Rules:

  • Items in exclude are skipped entirely.
  • Items whose weight is <= 0 (or non-finite) are never chosen.
  • count is clamped to the number of eligible items, so the result holds exactly min(count, eligible) items (an empty list when nothing qualifies).

Uses the Efraimidis-Spirakis algorithm: each eligible item gets the key random^(1/weight) and the items with the count largest keys are returned. Pass a seeded random for deterministic output. Result order is by descending key (most strongly selected first), not input order.

Example:

final List<String> picked = weightedSubset<String>(
  <String>['a', 'b', 'c'],
  count: 2,
  weight: (String s) => s == 'a' ? 10 : 1, // 'a' favored
  random: Random(7),
);
// picked.length == 2; 'a' chosen far more often across seeds

Audited: 2026-06-12 11:26 EDT

Implementation

List<T> weightedSubset<T>(
  List<T> items, {
  required int count,
  required double Function(T) weight,
  Set<T> exclude = const <Never>{},
  Random? random,
}) {
  if (count <= 0) return <T>[];
  final Random rng = random ?? Random();
  final List<_KeyedItem<T>> keyed = _keyEligible<T>(items, weight, exclude, rng);
  // Largest keys first; clamp the take to however many items actually qualified.
  keyed.sort((_KeyedItem<T> a, _KeyedItem<T> b) => b.key.compareTo(a.key));
  final int take = count < keyed.length ? count : keyed.length;
  return <T>[for (int i = 0; i < take; i++) keyed[i].item];
}