ExamplesBy LevelBy TopicLearning Paths
027 Intermediate GitHub
← 026028 →

027 — Group the Elements of a Set into Disjoint Subsets

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "027 — Group the Elements of a Set into Disjoint Subsets" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Partitioning a set into groups of specified sizes (OCaml 99 Problems #27) — for example, dividing 9 people into groups of 2, 3, and 4 — generalizes the combinations problem. Key difference from OCaml: 1. **List.mem vs HashSet**: OCaml's `List.filter ... not (List.mem x combo)` is O(n·k) per combination. Rust should use a `HashSet` for O(1) membership testing when removing selected elements.

Tutorial

The Problem

Partitioning a set into groups of specified sizes (OCaml 99 Problems #27) — for example, dividing 9 people into groups of 2, 3, and 4 — generalizes the combinations problem. This is multinomial selection: choose the first group, then choose the second group from the remainder, and so on. The number of ways to partition n elements into groups of sizes k1, k2, ..., km is the multinomial coefficient n! / (k1! · k2! · ... · km!).

This problem appears in sports scheduling (dividing teams into pools), committee selection, machine learning data splitting (train/validation/test), and parallel task distribution. The recursive structure — select one group, recurse on the rest — is a generalization of backtracking.

🎯 Learning Outcomes

  • • Compose the combinations operation recursively to form disjoint groups
  • • Understand multinomial coefficients as iterated binomial coefficients
  • • Handle groups of different sizes specified as a list
  • • Recognize partitioning as a key operation in algorithm design
  • • Use the combinations result from example 026 as a building block
  • • Build group-by-size by iterating through sizes and using combinations to select each group from the remaining elements
  • • The total number of groupings is the multinomial coefficient: n! / (k1! k2! ... * km!)

    • Code Example

    #![allow(clippy::all)]
// Partition a list into disjoint groups of the given sizes (OCaml 99 Problems #27),
// composing combinations() to select each group in turn.
fn combinations<T: Clone + PartialEq>(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
        }
    }
}

pub fn group<T: Clone + PartialEq>(list: &[T], sizes: &[usize]) -> Vec<Vec<Vec<T>>> {
    match sizes.split_first() {
        None => vec![vec![]],
        Some((&k, rest)) => {
            let mut result = Vec::new();
            for combo in combinations(k, list) {
                let remaining: Vec<T> = list.iter().filter(|x| !combo.contains(x)).cloned().collect();
                for sub in group(&remaining, rest) {
                    let mut g = vec![combo.clone()];
                    g.extend(sub);
                    result.push(g);
                }
            }
            result
        }
    }
}

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

    #[test]
    fn test_group_counts_match_multinomial_coefficient() {
        // C(3,1) * C(2,2) = 3 * 1 = 3
        assert_eq!(group(&[1, 2, 3], &[1, 2]).len(), 3);
    }

    #[test]
    fn test_each_grouping_partitions_the_original_set() {
        let groupings = group(&[1, 2, 3, 4], &[2, 2]);
        for grouping in &groupings {
            let flattened: HashSet<_> = grouping.iter().flatten().collect();
            assert_eq!(flattened, [1, 2, 3, 4].iter().collect());
            assert_eq!(grouping.len(), 2);
            for g in grouping {
                assert_eq!(g.len(), 2);
            }
        }
    }

    #[test]
    fn test_larger_grouping_count() {
        // C(9,2) * C(7,3) * C(4,4) = 36 * 35 * 1 = 1260
        let list: Vec<i32> = (1..=9).collect();
        assert_eq!(group(&list, &[2, 3, 4]).len(), 1260);
    }

    #[test]
    fn test_empty_sizes_yields_one_empty_grouping() {
        assert_eq!(group(&[1, 2, 3], &[]), vec![Vec::<Vec<i32>>::new()]);
    }
}

    Key Differences

  • List.mem vs HashSet: OCaml's List.filter ... not (List.mem x combo) is O(n·k) per combination. Rust should use a HashSet for O(1) membership testing when removing selected elements.
  • Index-based removal: Rust can track which elements remain by their indices rather than values, avoiding the equality check for non-Eq types.
  • Clone depth: Each partition result contains clones of the original elements. Rust's clone cost scales with the partition depth. OCaml shares structure via GC.
  • Explosion in output size: For 9 elements in groups of 2, 3, 4, there are C(9,2)·C(7,3)·C(4,4) = 36·35·1 = 1260 partitions. Large inputs explode quickly — always check the expected output size.
  • Recursive composition: Both implementations select a group of size k using combinations, then recurse on the remainder. The structure is identical — composition of previous solutions.
  • Element removal: Removing selected elements from the pool uses different idioms: OCaml uses List.filter (fun x -> not (List.mem x c)) (O(k·n)); Rust uses index-based exclusion or HashSet.
  • Result type: Vec<Vec<Vec<T>>> in Rust (list of groupings, each grouping is a list of groups). Deeply nested types benefit from type aliases for readability.

    • OCaml Approach

    OCaml's version: let group lst sizes = let rec aux lst sizes = match sizes with | [] -> [[]] | k :: rest -> List.concat_map (fun combo -> let remaining = List.filter (fun x -> not (List.mem x combo)) lst in List.map (fun groups -> combo :: groups) (aux remaining rest)) (combinations k lst) in aux lst sizes. This selects a combination of size k, removes those elements from the pool, then recursively groups the remainder.

    OCaml's group operation: let group list sizes = match sizes with | [] -> [[]] | k :: ks -> List.concat_map (fun c -> List.map (fun g -> c :: g) (group (List.filter (fun x -> not (List.mem x c)) list) ks)) (combinations k list). For each combination of size k, recursively group the remaining elements. The multinomial coefficient n! / (k1! · k2! · ... · km!) counts the results.

    Full Source

    #![allow(clippy::all)]
// Partition a list into disjoint groups of the given sizes (OCaml 99 Problems #27),
// composing combinations() to select each group in turn.
fn combinations<T: Clone + PartialEq>(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
        }
    }
}

pub fn group<T: Clone + PartialEq>(list: &[T], sizes: &[usize]) -> Vec<Vec<Vec<T>>> {
    match sizes.split_first() {
        None => vec![vec![]],
        Some((&k, rest)) => {
            let mut result = Vec::new();
            for combo in combinations(k, list) {
                let remaining: Vec<T> = list.iter().filter(|x| !combo.contains(x)).cloned().collect();
                for sub in group(&remaining, rest) {
                    let mut g = vec![combo.clone()];
                    g.extend(sub);
                    result.push(g);
                }
            }
            result
        }
    }
}

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

    #[test]
    fn test_group_counts_match_multinomial_coefficient() {
        // C(3,1) * C(2,2) = 3 * 1 = 3
        assert_eq!(group(&[1, 2, 3], &[1, 2]).len(), 3);
    }

    #[test]
    fn test_each_grouping_partitions_the_original_set() {
        let groupings = group(&[1, 2, 3, 4], &[2, 2]);
        for grouping in &groupings {
            let flattened: HashSet<_> = grouping.iter().flatten().collect();
            assert_eq!(flattened, [1, 2, 3, 4].iter().collect());
            assert_eq!(grouping.len(), 2);
            for g in grouping {
                assert_eq!(g.len(), 2);
            }
        }
    }

    #[test]
    fn test_larger_grouping_count() {
        // C(9,2) * C(7,3) * C(4,4) = 36 * 35 * 1 = 1260
        let list: Vec<i32> = (1..=9).collect();
        assert_eq!(group(&list, &[2, 3, 4]).len(), 1260);
    }

    #[test]
    fn test_empty_sizes_yields_one_empty_grouping() {
        assert_eq!(group(&[1, 2, 3], &[]), vec![Vec::<Vec<i32>>::new()]);
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashSet;

    #[test]
    fn test_group_counts_match_multinomial_coefficient() {
        // C(3,1) * C(2,2) = 3 * 1 = 3
        assert_eq!(group(&[1, 2, 3], &[1, 2]).len(), 3);
    }

    #[test]
    fn test_each_grouping_partitions_the_original_set() {
        let groupings = group(&[1, 2, 3, 4], &[2, 2]);
        for grouping in &groupings {
            let flattened: HashSet<_> = grouping.iter().flatten().collect();
            assert_eq!(flattened, [1, 2, 3, 4].iter().collect());
            assert_eq!(grouping.len(), 2);
            for g in grouping {
                assert_eq!(g.len(), 2);
            }
        }
    }

    #[test]
    fn test_larger_grouping_count() {
        // C(9,2) * C(7,3) * C(4,4) = 36 * 35 * 1 = 1260
        let list: Vec<i32> = (1..=9).collect();
        assert_eq!(group(&list, &[2, 3, 4]).len(), 1260);
    }

    #[test]
    fn test_empty_sizes_yields_one_empty_grouping() {
        assert_eq!(group(&[1, 2, 3], &[]), vec![Vec::<Vec<i32>>::new()]);
    }
}

    Deep Comparison

    OCaml vs Rust: Group By Size

    Overview

    See the example.rs and example.ml files for detailed implementations.

    Key Differences

    AspectOCamlRust
    Type systemHindley-MilnerOwnership + traits
    MemoryGCZero-cost abstractions
    MutabilityExplicit refmut keyword
    Error handlingOption/ResultResult<T, E>

    See README.md for detailed comparison.

    Exercises

  • Equal groups: Specialize to equal_groups(list: &[i32], k: usize) -> Vec<Vec<Vec<i32>>> that divides the list into groups all of size k. Handle the case where list.len() % k != 0.
  • Count partitions: Write count_groups(n: u64, sizes: &[u64]) -> u64 that computes the number of partitions using the multinomial formula without generating them.
  • Round-robin tournament: Given 8 teams, generate all possible round-robin schedules by partitioning them into 4 pairs each round, for 7 rounds. Use the group function.
  • All permutations of groups: After generating all possible groupings, generate all distinct orderings of those groups (the multinomial coefficient counts unordered groups; ordered groups multiply by k1! k2! ...).
  • Balanced partition: Implement balanced_split<T: Clone>(list: &[T]) -> Vec<(Vec<T>, Vec<T>)> that generates all ways to split a list into two roughly equal halves.

    • Open Source Repos

    functional-rust

    View the source for this example on GitHub — OCaml and Rust side by side in the repo.

    Rust