gen_combinations/
lib.rs

1#![doc(html_root_url = "https://docs.rs/gen-combinations/0.1.0")]
2//! A general combination generator that iterates over all possible combinations of a slice of items.
3//!
4//! Note that combinations are different than permutations in that this crate will not generate all possible orderings
5//! of those items.
6//!
7//! This crate does not check for uniqueness among the items; if this is desired, it is left up to the user to ensure that
8//! the items are unique before passing them to [`CombinationIterator::new`].
9//! 
10//! [`CombinationIterator::new`]: struct.CombinationIterator.html#method.new
11
12/// Iterates over all possible combinations of items.
13/// 
14/// The combinations are of immutable references to the items.
15/// 
16/// # Examples
17/// 
18/// ```
19/// use gen_combinations::CombinationIterator;
20/// 
21/// let items = [1, 2, 3];
22/// for combo in CombinationIterator::new(&items, 2) {
23///     println!("{:?}", combo);
24///     // [1, 2]
25///     // [1, 3]
26///     // [2, 3]
27/// }
28/// ```
29#[derive(Debug)]
30pub struct CombinationIterator<'a, T> {
31    items: &'a [T],
32    indices: Vec<usize>,
33}
34
35impl<T> CombinationIterator<'_, T> {
36    /// Creates an iterator over combinations of `items` with length `n`.
37    /// 
38    /// If `n` is 0 or greater than `items.len()`, the iterator will produce no values.
39    pub fn new(items: &[T], n: usize) -> CombinationIterator<T> {
40        let indices = (0..n).collect();
41        CombinationIterator { items, indices }
42    }
43}
44
45impl<'a, T> Iterator for CombinationIterator<'a, T> {
46    type Item = Vec<&'a T>;
47
48    fn next(&mut self) -> Option<Vec<&'a T>> {
49        if self.indices.is_empty() || self.indices.len() > self.items.len() {
50            None
51        } else {
52            let ret = self.indices.iter().map(|i| &(self.items[*i])).collect();
53            for i in (0..self.indices.len()).rev() {
54                if self.indices[i] < self.items.len() - (self.indices.len() - i) {
55                    self.indices[i] += 1;
56                    for j in i..self.indices.len() {
57                        self.indices[j] = self.indices[i] + (j - i);
58                    }
59                    return Some(ret);
60                }
61            }
62            self.indices.clear(); // next iteration will see that self.indices is empty and stop
63            Some(ret)
64        }
65    }
66}
67
68#[test]
69fn generate_combinations() {
70    let items = [1, 2, 3];
71    let mut c = CombinationIterator::new(&items, 2);
72    assert_eq!(c.next(), Some(vec![&1, &2]));
73    assert_eq!(c.next(), Some(vec![&1, &3]));
74    assert_eq!(c.next(), Some(vec![&2, &3]));
75    assert_eq!(c.next(), None);
76}
77
78#[test]
79fn generate_more_combinations() {
80    let items = [1, 2, 3, 4, 5];
81    let mut c = CombinationIterator::new(&items, 3);
82    assert_eq!(c.next(), Some(vec![&1, &2, &3]));
83    assert_eq!(c.next(), Some(vec![&1, &2, &4]));
84    assert_eq!(c.next(), Some(vec![&1, &2, &5]));
85    assert_eq!(c.next(), Some(vec![&1, &3, &4]));
86    assert_eq!(c.next(), Some(vec![&1, &3, &5]));
87    assert_eq!(c.next(), Some(vec![&1, &4, &5]));
88    assert_eq!(c.next(), Some(vec![&2, &3, &4]));
89    assert_eq!(c.next(), Some(vec![&2, &3, &5]));
90    assert_eq!(c.next(), Some(vec![&2, &4, &5]));
91    assert_eq!(c.next(), Some(vec![&3, &4, &5]));
92    assert_eq!(c.next(), None);
93}
94
95#[test]
96fn generate_combinations_of_things_that_arent_copy_just_to_be_sure() {
97    let items = [String::from("one"), String::from("two"), String::from("yeet")];
98    let mut c = CombinationIterator::new(&items, 2);
99    assert_eq!(c.next(), Some(vec![&String::from("one"), &String::from("two")]));
100    assert_eq!(c.next(), Some(vec![&String::from("one"), &String::from("yeet")]));
101    assert_eq!(c.next(), Some(vec![&String::from("two"), &String::from("yeet")]));
102    assert_eq!(c.next(), None);
103}
104
105#[test]
106fn misuse_arguments() {
107    let items = [1, 2, 3];
108    let mut c = CombinationIterator::new(&items, 500);
109    assert_eq!(c.next(), None);
110
111    let mut c = CombinationIterator::new(&items, 0);
112    assert_eq!(c.next(), None);
113}
gen_combinations/lib.rs

gen_combinations/
lib.rs
