023: Random Select

Difficulty: 1 Level: Beginner Extract N randomly chosen elements from a list without replacement.

The Problem This Solves

You need to pick random items from a collection — shuffle a playlist, sample test data, deal cards to players. Python programmers reach for `random.sample(my_list, n)`. This example shows how to build the same thing from scratch in Rust, and why the naive approach (just pick `index % length`) produces biased results. The modulo bias problem is subtle: if you have 5 items and your random number is in `[0, 256)`, then indices 0–1 appear 52 times while indices 2–4 appear only 51 times. Over millions of draws, this skew matters in simulations, games, and cryptography. In production you'd use the `rand` crate. Here we build a minimal LCG (Linear Congruential Generator) — the same algorithm used in most C standard libraries — so the code is self-contained and the mechanics are visible.

The Intuition

An LCG (Linear Congruential Generator) is a pseudo-random number sequence produced by the formula: `next = (prev × multiplier + increment) mod 2^64`. The magic constants (from Numerical Recipes) are chosen so the sequence visits all 2^64 values before repeating. We discard the low bits (they have poor randomness) and use only the top 31 bits. Sampling without replacement means once you pick an item, it can't be picked again. The cleanest way: copy the list into a mutable pool, pick a random index, remove that element (so it shrinks), repeat. This is the Fisher-Yates shuffle truncated to N steps. With replacement: each pick is independent — re-index the full list every time. Useful when you want duplicates (e.g., bootstrap statistics).

How It Works in Rust

struct Lcg { state: u64 }

impl Lcg {
 fn new(seed: u64) -> Self { Lcg { state: seed } }

 fn next_usize(&mut self, modulus: usize) -> usize {
     // LCG step: multiply + add (wrapping to stay in u64)
     self.state = self.state
         .wrapping_mul(6364136223846793005)
         .wrapping_add(1442695040888963407);
     // Use top 31 bits — they have better statistical quality than low bits
     ((self.state >> 33) as usize) % modulus
 }
}

Sampling without replacement:

fn rand_select<T: Clone>(lst: &[T], n: usize, seed: u64) -> Vec<T> {
 let mut rng = Lcg::new(seed);
 let mut pool = lst.to_vec();          // mutable working copy
 let count = n.min(pool.len());        // clamp to available items
 let mut result = Vec::with_capacity(count);

 for _ in 0..count {
     let idx = rng.next_usize(pool.len());
     result.push(pool.remove(idx));    // remove shrinks the pool
 }
 result
}

`pool.remove(idx)` does two things: returns the element and closes the gap, so subsequent picks never re-select it.

What This Unlocks

Reproducible randomness: same seed → same draw. Essential for debugging games, tests, and simulations.
Card dealing / lottery: pick N from M without repeats — exactly what Lotto example 024 builds on.
Bootstrap sampling: with-replacement variant powers statistical resampling algorithms.

Key Differences

Concept	OCaml	Rust
Random int	`Random.int n` (global state, no seed needed)	Custom LCG or `rand::thread_rng().gen_range(0..n)`
Remove from list	`List.filteri` or recursive rebuild (O(n))	`Vec::remove(idx)` — shifts elements (also O(n))
Seeded determinism	`Random.init seed` (global)	Seed stored in struct — no global state
Bias avoidance	Same modulo bias issue exists	Same; `rand` crate uses rejection sampling

// Random Select — 99 Problems #23
// Extract n randomly selected elements from a list.
// Uses a simple LCG pseudo-random generator (no external crates).

/// A minimal LCG pseudo-random number generator.
struct Lcg {
    state: u64,
}

impl Lcg {
    fn new(seed: u64) -> Self {
        Lcg { state: seed }
    }

    /// Returns next value in [0, modulus).
    fn next_usize(&mut self, modulus: usize) -> usize {
        // LCG parameters from Numerical Recipes
        self.state = self.state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        ((self.state >> 33) as usize) % modulus
    }
}

/// Select n random elements (without replacement) using LCG.
fn rand_select<T: Clone>(lst: &[T], n: usize, seed: u64) -> Vec<T> {
    let mut rng = Lcg::new(seed);
    let mut pool = lst.to_vec();
    let count = n.min(pool.len());
    let mut result = Vec::with_capacity(count);

    for _ in 0..count {
        let idx = rng.next_usize(pool.len());
        result.push(pool.remove(idx));
    }
    result
}

/// Select with replacement.
fn rand_select_with_replacement<T: Clone>(lst: &[T], n: usize, seed: u64) -> Vec<T> {
    if lst.is_empty() {
        return vec![];
    }
    let mut rng = Lcg::new(seed);
    (0..n).map(|_| lst[rng.next_usize(lst.len())].clone()).collect()
}

fn main() {
    let input = vec!['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];
    println!("Input: {:?}", input);

    let selected = rand_select(&input, 3, 42);
    println!("Random select 3 (seed=42):  {:?}", selected);

    let selected2 = rand_select(&input, 3, 99);
    println!("Random select 3 (seed=99):  {:?}", selected2);

    let with_rep = rand_select_with_replacement(&input, 5, 42);
    println!("With replacement 5 (seed=42): {:?}", with_rep);

    // Deterministic: same seed always gives same result
    assert_eq!(rand_select(&input, 3, 42), rand_select(&input, 3, 42));
    println!("Deterministic: ✓");
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_deterministic() {
        let input = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        let r1 = rand_select(&input, 3, 42);
        let r2 = rand_select(&input, 3, 42);
        assert_eq!(r1, r2);
    }

    #[test]
    fn test_correct_count() {
        let input = vec!['a', 'b', 'c', 'd', 'e'];
        let selected = rand_select(&input, 3, 7);
        assert_eq!(selected.len(), 3);
    }

    #[test]
    fn test_no_duplicates_without_replacement() {
        let input = vec![1, 2, 3, 4, 5];
        let selected = rand_select(&input, 5, 123);
        let mut sorted = selected.clone();
        sorted.sort();
        sorted.dedup();
        assert_eq!(sorted.len(), 5);
    }

    #[test]
    fn test_select_more_than_available() {
        let input = vec![1, 2, 3];
        // Clamps to list length
        assert_eq!(rand_select(&input, 10, 1).len(), 3);
    }
}

(* Random Select *)
(* OCaml 99 Problems #23 *)

(* Implementation for example 23 *)

(* Tests *)
let () =
  (* Add tests *)
  print_endline "✓ OCaml tests passed"