algos/cs/combinatorial/
subset_gen.rs

1//! Module for generating the power set (all subsets) of a slice using binary representation.
2//!
3//! This module provides:
4//! - An eager function `power_set` that returns all subsets as a Vec<Vec<T>>.
5//! - A lazy iterator `PowerSet` (with helper function `power_set_iter`) that yields subsets one by one.
6//!
7//! The subsets are generated by interpreting the numbers 0..2ⁿ as bit masks, where the i‑th bit
8//! indicates whether the i‑th element is included.
9//!
10//! # Examples
11//!
12//! Eager usage:
13//!
14//! ```
15//! use algos::cs::combinatorial::subset_gen::power_set;
16//!
17//! let items = vec![1, 2, 3];
18//! let subsets = power_set(&items);
19//! // For 3 elements, there are 2^3 = 8 subsets.
20//! assert_eq!(subsets.len(), 8);
21//! assert!(subsets.contains(&vec![]));
22//! assert!(subsets.contains(&vec![1, 2, 3]));
23//! ```
24//!
25//! Lazy usage:
26//!
27//! ```
28//! use algos::cs::combinatorial::subset_gen::power_set_iter;
29//!
30//! let items = vec!['a', 'b'];
31//! let subsets: Vec<_> = power_set_iter(&items).collect();
32//! assert_eq!(subsets.len(), 4);
33//! assert!(subsets.contains(&vec![]));
34//! assert!(subsets.contains(&vec!['a', 'b']));
35//! ```
36
37/// Returns all possible subsets of the given slice.
38pub fn power_set<T: Clone>(elements: &[T]) -> Vec<Vec<T>> {
39    let n = elements.len();
40    let total = 1 << n;
41    let mut result = Vec::with_capacity(total);
42
43    for mask in 0..total {
44        let mut subset = Vec::new();
45        for (i, item) in elements.iter().enumerate() {
46            if (mask & (1 << i)) != 0 {
47                subset.push(item.clone());
48            }
49        }
50        result.push(subset);
51    }
52    result
53}
54
55/// An iterator that lazily generates all subsets of a slice.
56pub struct PowerSet<'a, T> {
57    elements: &'a [T],
58    current: usize,
59    total: usize,
60}
61
62impl<'a, T> PowerSet<'a, T> {
63    fn new(elements: &'a [T]) -> Self {
64        PowerSet {
65            elements,
66            current: 0,
67            total: 1 << elements.len(),
68        }
69    }
70}
71
72impl<T: Clone> Iterator for PowerSet<'_, T> {
73    type Item = Vec<T>;
74
75    fn next(&mut self) -> Option<Self::Item> {
76        if self.current >= self.total {
77            return None;
78        }
79
80        let mut subset = Vec::new();
81        for (i, item) in self.elements.iter().enumerate() {
82            if (self.current & (1 << i)) != 0 {
83                subset.push(item.clone());
84            }
85        }
86
87        self.current += 1;
88        Some(subset)
89    }
90
91    fn size_hint(&self) -> (usize, Option<usize>) {
92        let remaining = self.total - self.current;
93        (remaining, Some(remaining))
94    }
95}
96
97/// Returns an iterator that lazily generates all subsets of the given slice.
98pub fn power_set_iter<T>(elements: &[T]) -> PowerSet<T> {
99    PowerSet::new(elements)
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn test_power_set_empty() {
108        let empty: Vec<i32> = vec![];
109        let subsets = power_set(&empty);
110        assert_eq!(subsets.len(), 1);
111        assert_eq!(subsets[0], vec![]);
112    }
113
114    #[test]
115    fn test_power_set_single() {
116        let items = vec![42];
117        let subsets = power_set(&items);
118        assert_eq!(subsets.len(), 2);
119        assert!(subsets.contains(&vec![]));
120        assert!(subsets.contains(&vec![42]));
121    }
122
123    #[test]
124    fn test_power_set_multiple() {
125        let items = vec![1, 2, 3];
126        let subsets = power_set(&items);
127        assert_eq!(subsets.len(), 8);
128        assert!(subsets.contains(&vec![]));
129        assert!(subsets.contains(&vec![1]));
130        assert!(subsets.contains(&vec![2]));
131        assert!(subsets.contains(&vec![3]));
132        assert!(subsets.contains(&vec![1, 2]));
133        assert!(subsets.contains(&vec![1, 3]));
134        assert!(subsets.contains(&vec![2, 3]));
135        assert!(subsets.contains(&vec![1, 2, 3]));
136    }
137
138    #[test]
139    fn test_power_set_iter() {
140        let items = vec!['a', 'b'];
141        let subsets: Vec<_> = power_set_iter(&items).collect();
142        assert_eq!(subsets.len(), 4);
143        assert!(subsets.contains(&vec![]));
144        assert!(subsets.contains(&vec!['a']));
145        assert!(subsets.contains(&vec!['b']));
146        assert!(subsets.contains(&vec!['a', 'b']));
147    }
148
149    #[test]
150    fn test_size_hint() {
151        let items = vec![1, 2, 3];
152        let mut iter = power_set_iter(&items);
153        assert_eq!(iter.size_hint(), (8, Some(8)));
154        iter.next();
155        assert_eq!(iter.size_hint(), (7, Some(7)));
156    }
157}
algos/cs/combinatorial/subset_gen.rs

algos/cs/combinatorial/
subset_gen.rs
