How does `rand::seq::IteratorRandom::choose` enable random sampling from arbitrary iterators?

rand::seq::IteratorRandom::choose implements reservoir sampling (specifically Algorithm R) to select a random element from an iterator without knowing the iterator's length in advance, using constant memory and a single pass through the data. The key insight is that the method must work with any iterator—finite or infinite, sized or unsized—so it cannot collect all elements and pick one. Instead, it maintains a "reservoir" of the currently selected element and replaces it with each subsequent element with probability 1/n, where n is the number of elements seen so far. This ensures every element has an equal probability of being selected by the end. The trait extends Iterator with the choose method, meaning any iterator can be randomly sampled with .choose(&mut rng), making it ergonomic for one-off selection without intermediate allocations.

Basic Random Selection

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
fn main() {
    let items = vec
!["apple", "banana", "cherry", "date", "elderberry"];
    
    let mut rng = thread_rng();
    
    // Select one random element
    if let Some(choice) = items.iter().choose(&mut rng) {
        println!("Random fruit: {}", choice);
    }
}

choose returns Option<&Item>—None only if the iterator is empty.

Working with Arbitrary Iterators

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
fn main() {
    let mut rng = thread_rng();
    
    // Works with any iterator, not just collections
    let even_choice = (0..100).filter(|x| x % 2 == 0).choose(&mut rng);
    println!("Random even number: {:?}", even_choice);
    
    // Works with map transformations
    let doubled = (1..=10).map(|x| x * 2).choose(&mut rng);
    println!("Random doubled: {:?}", doubled);
    
    // Works with iterators that don't implement ExactSizeIterator
    let filtered = (1..).filter(|x| x % 7 == 0).take(1000).choose(&mut rng);
    println!("Random multiple of 7: {:?}", filtered);
}

The trait works with any Iterator, regardless of size hints or ExactSizeIterator.

The Reservoir Sampling Algorithm

use rand::Rng;
 
fn manual_choose<I, R>(iter: I, rng: &mut R) -> Option<I::Item>
where
    I: Iterator,
    R: Rng,
{
    let mut chosen = None;
    let mut count = 0u64;
    
    for item in iter {
        count += 1;
        
        // First element is always chosen
        // Subsequent elements replace with probability 1/count
        if count == 1 {
            chosen = Some(item);
        } else if rng.gen_range(0..count) == 0 {
            chosen = Some(item);
        }
    }
    
    chosen
}
 
fn main() {
    use rand::thread_rng;
    let mut rng = thread_rng();
    
    let result = (1..=100).choose(&mut rng);
    println!("Result: {:?}", result);
    
    let manual_result = manual_choose(1..=100, &mut rng);
    println!("Manual result: {:?}", manual_result);
}

The algorithm ensures each element has 1/n probability of being selected after n elements.

Probability Distribution

use rand::seq::IteratorRandom;
use rand::thread_rng;
use std::collections::HashMap;
 
fn main() {
    let mut rng = thread_rng();
    let mut counts: HashMap<i32, u32> = HashMap::new();
    
    // Run many trials to verify uniform distribution
    for _ in 0..100_000 {
        if let Some(choice) = (1..=5).choose(&mut rng) {
            *counts.entry(choice).or_insert(0) += 1;
        }
    }
    
    for i in 1..=5 {
        let count = counts.get(&i).unwrap_or(&0);
        let percentage = (*count as f64 / 100_000.0) * 100.0;
        println!("{}: {:.1}%", i, percentage);
    }
}

Each element has equal probability of being selected.

Choosing Multiple Elements

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
fn main() {
    let mut rng = thread_rng();
    
    // Choose multiple elements
    let chosen: Vec<_> = (1..=100).choose_multiple(&mut rng, 5);
    println!("5 random numbers: {:?}", chosen);
    
    // Choose up to the length of the iterator
    let chosen: Vec<_> = (1..=3).choose_multiple(&mut rng, 10);
    println!("Chosen from small set: {:?}", chosen);
    // Returns at most 3 elements since that's all there are
    
    // Works with any iterator
    let words = vec
!["alpha", "beta", "gamma", "delta", "epsilon"];
    let chosen: Vec<_> = words.iter().choose_multiple(&mut rng, 3);
    println!("3 random words: {:?}", chosen);
}

choose_multiple uses reservoir sampling to select multiple elements uniformly.

Weighted Random Selection

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
fn main() {
    let mut rng = thread_rng();
    
    let items = vec
!["a", "b", "c", "d"];
    let weights = vec
![1u32, 2, 3, 4];
    
    // Weighted selection - elements with higher weights are more likely
    let chosen = items.iter().choose_weighted(&mut rng, |item| {
        let idx = items.iter().position(|&x| x == *item).unwrap();
        weights[idx]
    });
    
    println!("Weighted choice: {:?}", chosen);
    
    // Distribution test
    let mut counts: HashMap<&str, u32> = HashMap::new();
    for _ in 0..10_000 {
        let choice = items.iter()
            .choose_weighted(&mut rng, |&&item| {
                let idx = items.iter().position(|&x| x == item).unwrap();
                weights[idx]
            })
            .unwrap();
        *counts.entry(choice).or_insert(0) += 1;
    }
    
    for (item, count) in counts {
        println!("{}: {} (expected ~{})", item, count, 10_000 * weights[items.iter().position(|&x| x == item).unwrap()] / 10);
    }
}

choose_weighted samples proportionally to provided weights.

Custom Iterator Types

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
// Custom iterator that yields Fibonacci numbers
struct Fibonacci {
    a: u64,
    b: u64,
}
 
impl Fibonacci {
    fn new() -> Self {
        Self { a: 0, b: 1 }
    }
}
 
impl Iterator for Fibonacci {
    type Item = u64;
    
    fn next(&mut self) -> Option<Self::Item> {
        let current = self.a;
        self.a = self.b;
        self.b = current + self.b;
        Some(current)
    }
}
 
fn main() {
    let mut rng = thread_rng();
    
    // Choose from an infinite iterator
    let chosen = Fibonacci::new().take(100).choose(&mut rng);
    println!("Random Fibonacci number: {:?}", chosen);
    
    // You could even choose from the infinite sequence
    // (but it would never terminate)
    // let infinite_choice = Fibonacci::new().choose(&mut rng); // Never returns!
}

choose works with custom iterators—just implement Iterator.

Efficiency Considerations

use rand::seq::IteratorRandom;
use rand::thread_rng;
use std::time::Instant;
 
fn main() {
    let mut rng = thread_rng();
    
    // compare: collecting all vs. choose
    let start = Instant::now();
    let _ = (0..1_000_000).collect::<Vec<_>>().choose(&mut rng);
    let collect_time = start.elapsed();
    
    let start = Instant::now();
    let _ = (0..1_000_000).choose(&mut rng);
    let choose_time = start.elapsed();
    
    println!("collect + choose: {:?}", collect_time);
    println!("choose directly: {:?}", choose_time);
    println!("choose uses O(1) memory; collect uses O(n) memory");
}

choose uses constant memory; collecting uses linear memory.

Choosing with Cloned Elements

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
fn main() {
    let mut rng = thread_rng();
    
    let items = vec
!["alpha".to_string(), "beta".to_string(), "gamma".to_string()];
    
    // choose returns &String
    let reference = items.iter().choose(&mut rng);
    println!("Reference: {:?}", reference);
    
    // choose_cloned returns String
    let cloned = items.iter().choose_cloned(&mut rng);
    println!("Cloned: {:?}", cloned);
    
    // Alternative: collect then choose
    let owned = items.into_iter().collect::<Vec<_>>().choose(&mut rng);
    println!("Owned: {:?}", owned);
}

choose_cloned avoids borrowing when you need ownership of the selected element.

Choosing from File Lines

use rand::seq::IteratorRandom;
use rand::thread_rng;
use std::io::BufRead;
 
fn main() -> std::io::Result<()> {
    let mut rng = thread_rng();
    
    // Read lines from stdin
    let stdin = std::io::stdin();
    let reader = stdin.lock();
    
    // Choose a random line without loading all lines into memory
    let random_line = reader.lines()
        .filter_map(|line| line.ok())
        .choose(&mut rng);
    
    match random_line {
        Some(line) => println!("Random line: {}", line),
        None => println!("No lines available"),
    }
    
    Ok(())
}

choose works with streaming data that doesn't fit in memory.

Implementing Random Selection for Your Types

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
#[derive(Debug)]
struct Card {
    suit: &'static str,
    rank: &'static str,
}
 
fn main() {
    let mut rng = thread_rng();
    
    let deck: Vec<Card> = vec
![
        Card { suit: "hearts", rank: "ace" },
        Card { suit: "hearts", rank: "king" },
        Card { suit: "diamonds", rank: "queen" },
        Card { suit: "clubs", rank: "jack" },
        Card { suit: "spades", rank: "10" },
    ];
    
    // Draw one card
    let drawn = deck.iter().choose(&mut rng);
    println!("Drawn: {:?}", drawn);
    
    // Draw a hand of 3 cards
    let hand: Vec<_> = deck.iter().choose_multiple(&mut rng, 3);
    println!("Hand: {:?}", hand);
}

Any iterator over your types can use choose.

Performance on Different Iterator Types

use rand::seq::IteratorRandom;
use rand::thread_rng;
use std::time::Instant;
 
fn main() {
    let mut rng = thread_rng();
    
    // Vector iterator - knows size, but choose still uses reservoir sampling
    let vec = (0..100_000).collect::<Vec<_>>();
    let start = Instant::now();
    let _ = vec.iter().choose(&mut rng);
    println!("Vec: {:?}", start.elapsed());
    
    // Range iterator - doesn't know exact size
    let start = Instant::now();
    let _ = (0..100_000).choose(&mut rng);
    println!("Range: {:?}", start.elapsed());
    
    // Filtered iterator - can't know size
    let start = Instant::now();
    let _ = (0..100_000).filter(|x| x % 2 == 0).choose(&mut rng);
    println!("Filtered: {:?}", start.elapsed());
}

choose has consistent behavior regardless of iterator type.

Edge Cases

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
fn main() {
    let mut rng = thread_rng();
    
    // Empty iterator returns None
    let empty: Vec<i32> = vec
![];
    let result = empty.iter().choose(&mut rng);
    println!("Empty: {:?}", result);  // None
    
    // Single element iterator
    let single = vec
!["only"];
    let result = single.iter().choose(&mut rng);
    println!("Single: {:?}", result);  // Some("only")
    
    // choose_multiple with amount > length
    let small = vec
![1, 2, 3];
    let chosen: Vec<_> = small.iter().choose_multiple(&mut rng, 10);
    println!("More than available: {:?}", chosen);  // [1, 2, 3] in random order
}

choose handles edge cases gracefully.

Choose with Mutable References

use rand::seq::IteratorRandom;
use rand::thread_rng;
 
fn main() {
    let mut rng = thread_rng();
    
    let mut numbers = vec
![1, 2, 3, 4, 5];
    
    // Get mutable reference to chosen element
    if let Some(chosen) = numbers.iter_mut().choose(&mut rng) {
        *chosen += 100;
    }
    
    println!("Modified: {:?}", numbers);
}

iter_mut().choose() returns Option<&mut Item> for mutation.

Choosing from HashMap

use rand::seq::IteratorRandom;
use rand::thread_rng;
use std::collections::HashMap;
 
fn main() {
    let mut rng = thread_rng();
    
    let mut scores: HashMap<&str, u32> = HashMap::new();
    scores.insert("alice", 95);
    scores.insert("bob", 87);
    scores.insert("charlie", 92);
    
    // Choose a random key-value pair
    if let Some((name, score)) = scores.iter().choose(&mut rng) {
        println!("Random entry: {} -> {}", name, score);
    }
    
    // Choose a random key
    if let Some(key) = scores.keys().choose(&mut rng) {
        println!("Random key: {}", key);
    }
    
    // Choose a random value
    if let Some(value) = scores.values().choose(&mut rng) {
        println!("Random value: {}", value);
    }
}

choose works with any collection that implements Iterator.

Using with Custom RNG

use rand::seq::IteratorRandom;
use rand::rngs::StdRng;
use rand::SeedableRng;
 
fn main() {
    // Deterministic RNG for reproducible results
    let mut rng = StdRng::seed_from_u64(42);
    
    let first_run: Vec<_> = (1..=100).choose_multiple(&mut rng, 5);
    
    let mut rng = StdRng::seed_from_u64(42);
    let second_run: Vec<_> = (1..=100).choose_multiple(&mut rng, 5);
    
    println!("First: {:?}", first_run);
    println!("Second: {:?}", second_run);
    println!("Same seed = same results: {}", first_run == second_run);
}

Seeded RNG produces reproducible selections.

Synthesis

Algorithm behavior:

Elements Seen	Probability New Element is Chosen
1	1/1 = 100%
2	1/2 = 50%
3	1/3 ≈ 33%
n	1/n

Each element has equal 1/n final probability.

Method comparison:

Method	Returns	Memory	Use Case
`choose`	`Option<Item>`	O(1)	Single element
`choose_cloned`	`Option<Item>` (owned)	O(1)	Single owned element
`choose_multiple`	`Vec<Item>`	O(k)	Multiple elements
`choose_weighted`	`Option<Item>`	O(1)	Weighted selection

Key insight: IteratorRandom::choose solves a fundamental problem—selecting uniformly from an unknown-sized sequence using only a single pass. The reservoir sampling algorithm (Algorithm R) guarantees that after processing n elements, each element has exactly 1/n probability of being selected, proven by induction: element 1 is chosen initially with probability 1, then replaced by element 2 with probability 1/2 (so element 1's final probability is 1 × 1/2 = 1/2), and so on. This matters because real-world iterators often don't (or can't) know their size—a file's lines, a network stream's messages, or a filter chain's output—making "collect and pick" impossible or prohibitively expensive. The trait extension pattern (trait IteratorRandom: Iterator) means any iterator gains this capability automatically, and the Rng parameter lets you control randomness source for testing or reproducibility. The weighted variant extends this to non-uniform distributions while maintaining the single-pass guarantee. For selecting multiple elements, choose_multiple uses reservoir sampling variant (Algorithm R for multiple reservoirs) that samples k elements with equal probability—a different algorithm than repeating choose k times, which would bias toward later elements.

How does rand::seq::IteratorRandom::choose enable random sampling from arbitrary iterators?