026 — Generate the Combinations of K Distinct Objects Chosen from N Elements
Tutorial Video
Text description (accessibility)
This video demonstrates the "026 — Generate the Combinations of K Distinct Objects Chosen from N Elements" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Generating all k-element subsets (combinations) of a set (OCaml 99 Problems #26) is a fundamental combinatorics problem. Key difference from OCaml: 1. **`@` vs extend**: OCaml's `@` concatenates two lists in O(|left|). Rust uses `result.extend(...)` which is O(|right|). For collecting into a flat `Vec<Vec<T>>`, Rust's approach avoids intermediate allocations.
Tutorial
The Problem
Generating all k-element subsets (combinations) of a set (OCaml 99 Problems #26) is a fundamental combinatorics problem. C(n, k) = n! / (k! · (n-k)!) is the number of ways to choose k elements from n without regard to order. The recursive structure — either include the first element (and choose k-1 from the rest) or skip it (and choose k from the rest) — is the textbook example of backtracking.
Combinations appear in feature selection for machine learning, generating test cases for pairwise testing, computing binomial coefficients, scheduling round-robin tournaments, and drug trial design. The recursive divide-and-conquer structure here is the basis for all backtracking algorithms.
🎯 Learning Outcomes
combinations(k, [h|t]) = [h|c] for c in combinations(k-1, t) ++ combinations(k, t)combinations(k, [h|t]) = [[h] + c for c in combinations(k-1, t)] ++ combinations(k, t)[[]]; k > remaining yields no combinations []Code Example
#![allow(clippy::all)]
// Generate all k-element combinations of a list (OCaml 99 Problems #26),
// via the classic include/exclude backtracking recursion.
pub fn combinations<T: Clone>(k: usize, list: &[T]) -> Vec<Vec<T>> {
if k == 0 {
return vec![vec![]];
}
match list.split_first() {
None => vec![],
Some((head, tail)) => {
let mut with_head: Vec<Vec<T>> = combinations(k - 1, tail)
.into_iter()
.map(|mut c| {
c.insert(0, head.clone());
c
})
.collect();
with_head.extend(combinations(k, tail));
with_head
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_combinations_of_2_from_3() {
assert_eq!(
combinations(2, &[1, 2, 3]),
vec![vec![1, 2], vec![1, 3], vec![2, 3]]
);
}
#[test]
fn test_k_zero_yields_one_empty_combination() {
assert_eq!(combinations(0, &[1, 2, 3]), vec![Vec::<i32>::new()]);
}
#[test]
fn test_k_greater_than_len_yields_none() {
let empty: Vec<Vec<i32>> = vec![];
assert_eq!(combinations(5, &[1, 2, 3]), empty);
}
#[test]
fn test_k_equals_len_yields_one_combination() {
assert_eq!(combinations(3, &[1, 2, 3]), vec![vec![1, 2, 3]]);
}
#[test]
fn test_count_matches_binomial_coefficient() {
// C(5, 2) = 10
assert_eq!(combinations(2, &[1, 2, 3, 4, 5]).len(), 10);
}
}Key Differences
@ vs extend**: OCaml's @ concatenates two lists in O(|left|). Rust uses result.extend(...) which is O(|right|). For collecting into a flat Vec<Vec<T>>, Rust's approach avoids intermediate allocations.combinations recursion is not tail-recursive in either language (it recurses on two branches).itertools crate provides (0..n).combinations(k) — use Itertools::combinations in production code. OCaml has no such standard facility.[h|c for c in combinations(k-1, t)] ++ combinations(k, t) is identical in both languages — include h with one fewer to choose, or skip h.C(n,k) growth:** The number of combinations grows as a binomial coefficient. For n=20, k=10, there are 184,756 combinations. Memory and time are O(C(n,k)) — this explodes quickly.map ... @ combinations k t (include-first). Rust typically builds includes then excludes in the same order. Result order differs from standard "lexicographic" combinations unless specifically sorted.OCaml Approach
OCaml's canonical version: let rec combinations k lst = match k, lst with | 0, _ -> [[]] | _, [] -> [] | k, x :: xs -> List.map (fun c -> x :: c) (combinations (k-1) xs) @ combinations k xs. The @ concatenates the two cases. This directly encodes the mathematical recurrence: C(k, n) = C(k-1, n-1) + C(k, n-1).
OCaml's combinations: let rec combinations k list = match k, list with | 0, _ -> [[]] | _, [] -> [] | k, h :: t -> List.map (fun c -> h :: c) (combinations (k-1) t) @ combinations k t. This is the include/exclude recursion: either include h in the combination (and choose k-1 more from the rest), or exclude it (choose k from the rest). The list monad (bind) makes this even more concise: let (>>=) l f = List.concat_map f l.
Full Source
#![allow(clippy::all)]
// Generate all k-element combinations of a list (OCaml 99 Problems #26),
// via the classic include/exclude backtracking recursion.
pub fn combinations<T: Clone>(k: usize, list: &[T]) -> Vec<Vec<T>> {
if k == 0 {
return vec![vec![]];
}
match list.split_first() {
None => vec![],
Some((head, tail)) => {
let mut with_head: Vec<Vec<T>> = combinations(k - 1, tail)
.into_iter()
.map(|mut c| {
c.insert(0, head.clone());
c
})
.collect();
with_head.extend(combinations(k, tail));
with_head
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_combinations_of_2_from_3() {
assert_eq!(
combinations(2, &[1, 2, 3]),
vec![vec![1, 2], vec![1, 3], vec![2, 3]]
);
}
#[test]
fn test_k_zero_yields_one_empty_combination() {
assert_eq!(combinations(0, &[1, 2, 3]), vec![Vec::<i32>::new()]);
}
#[test]
fn test_k_greater_than_len_yields_none() {
let empty: Vec<Vec<i32>> = vec![];
assert_eq!(combinations(5, &[1, 2, 3]), empty);
}
#[test]
fn test_k_equals_len_yields_one_combination() {
assert_eq!(combinations(3, &[1, 2, 3]), vec![vec![1, 2, 3]]);
}
#[test]
fn test_count_matches_binomial_coefficient() {
// C(5, 2) = 10
assert_eq!(combinations(2, &[1, 2, 3, 4, 5]).len(), 10);
}
}#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_combinations_of_2_from_3() {
assert_eq!(
combinations(2, &[1, 2, 3]),
vec![vec![1, 2], vec![1, 3], vec![2, 3]]
);
}
#[test]
fn test_k_zero_yields_one_empty_combination() {
assert_eq!(combinations(0, &[1, 2, 3]), vec![Vec::<i32>::new()]);
}
#[test]
fn test_k_greater_than_len_yields_none() {
let empty: Vec<Vec<i32>> = vec![];
assert_eq!(combinations(5, &[1, 2, 3]), empty);
}
#[test]
fn test_k_equals_len_yields_one_combination() {
assert_eq!(combinations(3, &[1, 2, 3]), vec![vec![1, 2, 3]]);
}
#[test]
fn test_count_matches_binomial_coefficient() {
// C(5, 2) = 10
assert_eq!(combinations(2, &[1, 2, 3, 4, 5]).len(), 10);
}
}Deep Comparison
OCaml vs Rust: Combinations
Overview
See the example.rs and example.ml files for detailed implementations.
Key Differences
| Aspect | OCaml | Rust |
|---|---|---|
| Type system | Hindley-Milner | Ownership + traits |
| Memory | GC | Zero-cost abstractions |
| Mutability | Explicit ref | mut keyword |
| Error handling | Option/Result | Result<T, E> |
See README.md for detailed comparison.
Exercises
combinations_with_rep(list: &[i32], k: usize) -> Vec<Vec<i32>> where elements can be chosen multiple times. The recursion changes to allow reusing elements.count_combinations(n: u64, k: u64) -> u64 using the multiplicative formula C(n,k) = n(n-1)...*(n-k+1) / k! without overflow. Use u128 or arbitrary precision.power_set(list: &[i32]) -> Vec<Vec<i32>> that returns all 2^n subsets. This is combinations(0) ++ combinations(1) ++ ... ++ combinations(n).combinations_with_rep<T: Clone>(list: &[T], k: usize) -> Vec<Vec<T>> where each element may be chosen more than once. The count is C(n+k-1, k).power_set<T: Clone>(list: &[T]) -> Vec<Vec<T>> returning all 2^n subsets. Use combinations(0) ++ combinations(1) ++ ... ++ combinations(n) or a direct recursive approach.