combinatorial/
combinations.rs

1use std::collections::BTreeSet;
2
3/// An iterator which generates combinations over a set of elements.
4///
5/// # Examples
6///
7/// ```
8/// use combinatorial::Combinations;
9///
10/// let mut abc_tuples = Combinations::of_size(vec!['a', 'b', 'c'], 2);
11/// assert_eq!(abc_tuples.next(), Some(vec!['a', 'b']));
12/// assert_eq!(abc_tuples.next(), Some(vec!['a', 'c']));
13/// assert_eq!(abc_tuples.next(), Some(vec!['b', 'c']));
14/// assert_eq!(abc_tuples.next(), None);
15///
16/// let ones_and_zeros: Vec<Vec<usize>> = Combinations::all(0..2).collect();
17/// assert_eq!(ones_and_zeros, vec![Vec::new(), vec![0], vec![1], vec![0, 1]]);
18/// ```
19pub struct Combinations<T> {
20    elements: Vec<T>,
21    positions: Vec<usize>,
22    all_sizes: bool,
23    done: bool,
24}
25
26/// Converts an iterable input into a sorted vector containing one of every unique item from the
27/// original iterable.
28fn iterable_to_sorted_set<T: Ord + Clone>(elements: impl IntoIterator<Item = T>) -> Vec<T> {
29    elements
30        .into_iter()
31        .collect::<BTreeSet<T>>()
32        .into_iter()
33        .collect::<Vec<T>>()
34}
35
36impl<T: Ord + Clone> Combinations<T> {
37    /// Creates a new `Combinations` iterator which will yield all combinations of the elements in
38    /// the given iterable.
39    ///
40    /// # Examples
41    ///
42    /// ```
43    /// use combinatorial::Combinations;
44    ///
45    /// let mut combos = Combinations::all(vec!["hello", "world"]).map(|str_vec| str_vec.join(" "));
46    /// assert_eq!(combos.next(), Some(String::from("")));
47    /// assert_eq!(combos.next(), Some(String::from("hello")));
48    /// assert_eq!(combos.next(), Some(String::from("world")));
49    /// assert_eq!(combos.next(), Some(String::from("hello world")));
50    /// assert_eq!(combos.next(), None);
51    ///
52    /// let mut combos = Combinations::all(1..1);
53    /// assert_eq!(combos.next(), Some(Vec::new()));
54    /// assert_eq!(combos.next(), None);
55    /// ```
56    pub fn all(elements: impl IntoIterator<Item = T>) -> Self {
57        Combinations {
58            elements: iterable_to_sorted_set(elements),
59            positions: Vec::new(),
60            all_sizes: true,
61            done: false,
62        }
63    }
64
65    /// Creates a new `Combinations` iterator which will yield all combinations with the specified
66    /// size from the elements in the given iterable.
67    ///
68    /// # Examples
69    ///
70    /// ```
71    /// use combinatorial::Combinations;
72    ///
73    /// let mut combos = Combinations::of_size(1..4, 2);
74    /// assert_eq!(combos.next(), Some(vec![1, 2]));
75    /// assert_eq!(combos.next(), Some(vec![1, 3]));
76    /// assert_eq!(combos.next(), Some(vec![2, 3]));
77    /// assert_eq!(combos.next(), None);
78    ///
79    /// let mut combos = Combinations::of_size('a'..'z', 0);
80    /// assert_eq!(combos.next(), Some(Vec::new()));
81    /// assert_eq!(combos.next(), None);
82    ///
83    /// let mut combos = Combinations::of_size(vec!["foo", "bar", "baz"], 4);
84    /// assert_eq!(combos.next(), None);
85    /// ```
86    pub fn of_size(elements: impl IntoIterator<Item = T>, size: usize) -> Self {
87        Combinations {
88            elements: iterable_to_sorted_set(elements),
89            positions: (0..size).collect(),
90            all_sizes: false,
91            done: false,
92        }
93    }
94
95    /// Adds another position indicator to the internal positions list and resets them to point to
96    /// the first `n` indices in order.
97    fn move_to_next_set_size(&mut self) -> bool {
98        if self.positions.len() >= self.elements.len() {
99            return false;
100        }
101        self.positions
102            .iter_mut()
103            .enumerate()
104            .for_each(|(index, pos)| *pos = index);
105        self.positions.push(self.positions.len());
106        true
107    }
108
109    /// Increments the internal positions to correspond to the indices of the next combination of
110    /// the same size.  If the positions are successfully incremented at the current combination
111    /// set size, then returns `true`.  Otherwise, returns `false`.
112    fn move_to_next_position(&mut self) -> bool {
113        if self.elements.len() == 0 {
114            return false;
115        }
116        let length = self.positions.len();
117        for index in (0..self.positions.len()).rev() {
118            let cur_position = *self.positions.get(index).unwrap();
119            if cur_position >= self.elements.len() - 1 {
120                continue;
121            }
122            if index == length - 1 || cur_position < self.positions.get(index + 1).unwrap() - 1 {
123                let mut next_position = cur_position + 1;
124                *self.positions.get_mut(index).unwrap() = next_position;
125                for i in index + 1..length {
126                    next_position += 1;
127                    *self.positions.get_mut(i).unwrap() = next_position;
128                }
129                return true;
130            }
131        }
132        false
133    }
134
135    /// Returns the current combination, if one exists and is valid.
136    fn get_current_combination(&mut self) -> Option<Vec<T>> {
137        if self.done || self.positions.len() > self.elements.len() {
138            return None;
139        }
140        Some(
141            self.positions
142                .iter()
143                .map(|p| self.elements.get(*p).unwrap().clone())
144                .collect::<Vec<T>>(),
145        )
146    }
147}
148
149impl<T: Ord + Clone> Iterator for Combinations<T> {
150    type Item = Vec<T>;
151
152    /// Returns the next combination and advances the internal iterator.
153    fn next(&mut self) -> Option<Self::Item> {
154        if self.done {
155            return None;
156        }
157        let combo = self.get_current_combination();
158        if self.move_to_next_position() == false {
159            if self.all_sizes == false || self.move_to_next_set_size() == false {
160                self.done = true;
161            }
162        }
163        combo
164    }
165}
166
167/// An iterator which generates combinations over a set of elements, with replacement.
168///
169/// # Examples
170///
171/// ```
172/// use combinatorial::CombinationsWithReplacement;
173///
174/// let mut abc_tuples = CombinationsWithReplacement::of_size(vec!['a', 'b', 'c'], 2);
175/// assert_eq!(abc_tuples.next(), Some(vec!['a', 'a']));
176/// assert_eq!(abc_tuples.next(), Some(vec!['a', 'b']));
177/// assert_eq!(abc_tuples.next(), Some(vec!['a', 'c']));
178/// assert_eq!(abc_tuples.next(), Some(vec!['b', 'b']));
179/// assert_eq!(abc_tuples.next(), Some(vec!['b', 'c']));
180/// assert_eq!(abc_tuples.next(), Some(vec!['c', 'c']));
181/// assert_eq!(abc_tuples.next(), None);
182///
183/// let mut ones_and_zeros = CombinationsWithReplacement::all(0..2);
184/// assert_eq!(ones_and_zeros.next(), Some(Vec::new()));
185/// assert_eq!(ones_and_zeros.next(), Some(vec![0]));
186/// assert_eq!(ones_and_zeros.next(), Some(vec![1]));
187/// assert_eq!(ones_and_zeros.next(), Some(vec![0, 0]));
188/// assert_eq!(ones_and_zeros.next(), Some(vec![0, 1]));
189/// assert_eq!(ones_and_zeros.next(), Some(vec![1, 1]));
190/// assert_eq!(ones_and_zeros.next(), None);
191/// ```
192pub struct CombinationsWithReplacement<T> {
193    elements: Vec<T>,
194    positions: Vec<usize>,
195    all_sizes: bool,
196    done: bool,
197}
198
199impl<T: Ord + Clone> CombinationsWithReplacement<T> {
200    /// Creates a new `CombinationsWithReplacement` iterator which will yield all combinations with
201    /// replacement of the elements in the given iterable.
202    ///
203    /// # Examples
204    ///
205    /// ```
206    /// use combinatorial::CombinationsWithReplacement;
207    ///
208    /// let mut combos = CombinationsWithReplacement::all(vec!["hello", "world"]).map(|str_vec| str_vec.join(" "));
209    /// assert_eq!(combos.next(), Some(String::from("")));
210    /// assert_eq!(combos.next(), Some(String::from("hello")));
211    /// assert_eq!(combos.next(), Some(String::from("world")));
212    /// assert_eq!(combos.next(), Some(String::from("hello hello")));
213    /// assert_eq!(combos.next(), Some(String::from("hello world")));
214    /// assert_eq!(combos.next(), Some(String::from("world world")));
215    /// assert_eq!(combos.next(), None);
216    ///
217    /// let mut combos = CombinationsWithReplacement::all(1..1);
218    /// assert_eq!(combos.next(), Some(Vec::new()));
219    /// assert_eq!(combos.next(), None);
220    /// ```
221    pub fn all(elements: impl IntoIterator<Item = T>) -> Self {
222        CombinationsWithReplacement {
223            elements: iterable_to_sorted_set(elements),
224            positions: Vec::new(),
225            all_sizes: true,
226            done: false,
227        }
228    }
229
230    /// Creates a new `CombinationsWithReplacement` iterator which will yield all combinations with
231    /// replacement of the specified size from the elements in the given iterable.
232    ///
233    /// # Examples
234    ///
235    /// ```
236    /// use combinatorial::CombinationsWithReplacement;
237    ///
238    /// let mut combos = CombinationsWithReplacement::of_size(1..4, 2);
239    /// assert_eq!(combos.next(), Some(vec![1, 1]));
240    /// assert_eq!(combos.next(), Some(vec![1, 2]));
241    /// assert_eq!(combos.next(), Some(vec![1, 3]));
242    /// assert_eq!(combos.next(), Some(vec![2, 2]));
243    /// assert_eq!(combos.next(), Some(vec![2, 3]));
244    /// assert_eq!(combos.next(), Some(vec![3, 3]));
245    /// assert_eq!(combos.next(), None);
246    ///
247    /// let mut combos = CombinationsWithReplacement::of_size('a'..'z', 0);
248    /// assert_eq!(combos.next(), Some(Vec::new()));
249    /// assert_eq!(combos.next(), None);
250    ///
251    /// let mut combos = CombinationsWithReplacement::of_size(vec!["foo", "bar", "baz"], 4);
252    /// assert_eq!(combos.next(), None);
253    /// ```
254    pub fn of_size(elements: impl IntoIterator<Item = T>, size: usize) -> Self {
255        CombinationsWithReplacement {
256            elements: iterable_to_sorted_set(elements),
257            positions: vec![0; size],
258            all_sizes: false,
259            done: false,
260        }
261    }
262
263    /// Adds another position indicator to the internal positions list and resets them to point to
264    /// the first index of the elements.
265    fn move_to_next_set_size(&mut self) -> bool {
266        if self.positions.len() >= self.elements.len() {
267            return false;
268        }
269        self.positions.iter_mut().for_each(|pos| *pos = 0);
270        self.positions.push(0);
271        true
272    }
273
274    /// Increments the internal positions to correspond to the indices of the next combination of
275    /// the same size.  If the positions are successfully incremented at the current combination
276    /// set size, then returns `true`.  Otherwise, returns `false`.
277    fn move_to_next_position(&mut self) -> bool {
278        if self.elements.len() == 0 {
279            return false;
280        }
281        let length = self.positions.len();
282        for index in (0..self.positions.len()).rev() {
283            let cur_position = *self.positions.get(index).unwrap();
284            if cur_position >= self.elements.len() - 1 {
285                // We only want to advance an earlier position if all later positions are already
286                // at the final element. Otherwise, we'd advance the latest position which is not
287                // yet at the final element.
288                continue;
289            }
290            let next_position = cur_position + 1;
291            // We know that `cur_position` is not at the final element, and any later positions
292            // must be at the final element, so we can unconditionally set the current and any
293            // subsequent positions to `next_position`.
294            for i in index..length {
295                *self.positions.get_mut(i).unwrap() = next_position;
296            }
297            return true;
298        }
299        false
300    }
301
302    /// Returns the current combination, if one exists and is valid.
303    fn get_current_combination(&mut self) -> Option<Vec<T>> {
304        if self.done || self.positions.len() > self.elements.len() {
305            return None;
306        }
307        Some(
308            self.positions
309                .iter()
310                .map(|p| self.elements.get(*p).unwrap().clone())
311                .collect::<Vec<T>>(),
312        )
313    }
314}
315
316impl<T: Ord + Clone> Iterator for CombinationsWithReplacement<T> {
317    type Item = Vec<T>;
318
319    /// Returns the next combination and advances the internal iterator.
320    fn next(&mut self) -> Option<Self::Item> {
321        if self.done {
322            return None;
323        }
324        let combo = self.get_current_combination();
325        if self.move_to_next_position() == false {
326            if self.all_sizes == false || self.move_to_next_set_size() == false {
327                self.done = true;
328            }
329        }
330        combo
331    }
332}
333
334#[cfg(test)]
335mod tests {
336    use super::*;
337
338    #[test]
339    fn test_combinations_iterable_to_sorted_set() {
340        assert_eq!(vec![1, 2, 3, 4], iterable_to_sorted_set(vec![1, 2, 3, 4]));
341        assert_eq!(vec![1, 2, 3, 4], iterable_to_sorted_set(1..5));
342        assert_eq!(
343            vec![1, 2, 3, 4].iter().collect::<Vec<&usize>>(),
344            iterable_to_sorted_set(vec![2, 3, 1, 4].iter())
345        );
346        assert_eq!(
347            vec![&1, &2, &3, &4],
348            iterable_to_sorted_set(&vec![2, 1, 3, 1, 4, 2, 2, 3])
349        );
350    }
351
352    #[test]
353    fn test_combinations_all() {
354        let combos = Combinations::all(vec![2, 4, 3, 1, 2, 2, 1].into_iter());
355        assert_eq!(combos.elements, vec![1, 2, 3, 4]);
356        assert_eq!(combos.positions, Vec::new());
357        assert_eq!(combos.all_sizes, true);
358        assert_eq!(combos.done, false);
359    }
360
361    #[test]
362    fn test_combinations_w_rep_all() {
363        let combos = CombinationsWithReplacement::all(vec![2, 4, 3, 1, 2, 2, 1].into_iter());
364        assert_eq!(combos.elements, vec![1, 2, 3, 4]);
365        assert_eq!(combos.positions, Vec::new());
366        assert_eq!(combos.all_sizes, true);
367        assert_eq!(combos.done, false);
368    }
369
370    #[test]
371    fn test_combinations_of_size() {
372        let combos = Combinations::of_size(vec![2, 4, 3, 1, 2, 2, 1].into_iter(), 3);
373        assert_eq!(combos.elements, vec![1, 2, 3, 4]);
374        assert_eq!(combos.positions, vec![0, 1, 2]);
375        assert_eq!(combos.all_sizes, false);
376        assert_eq!(combos.done, false);
377    }
378
379    #[test]
380    fn test_combinations_w_rep_of_size() {
381        let combos = CombinationsWithReplacement::of_size(vec![2, 4, 3, 1, 2, 2, 1].into_iter(), 3);
382        assert_eq!(combos.elements, vec![1, 2, 3, 4]);
383        assert_eq!(combos.positions, vec![0; 3]);
384        assert_eq!(combos.all_sizes, false);
385        assert_eq!(combos.done, false);
386    }
387
388    #[test]
389    fn test_combinations_move_to_next_set_size() {
390        let mut combos = Combinations::all(Vec::<i64>::new());
391        assert_eq!(combos.positions, Vec::new());
392        assert_eq!(combos.move_to_next_set_size(), false);
393        let mut combos = Combinations::all(vec![1]);
394        assert_eq!(combos.positions, Vec::new());
395        assert_eq!(combos.move_to_next_set_size(), true);
396        assert_eq!(combos.positions, vec![0]);
397        assert_eq!(combos.move_to_next_set_size(), false);
398        let mut combos = Combinations::all(vec![1, 2, 3, 4]);
399        assert_eq!(combos.positions, Vec::new());
400        assert_eq!(combos.move_to_next_set_size(), true);
401        assert_eq!(combos.positions, vec![0]);
402        combos.positions[0] = 4;
403        assert_eq!(combos.move_to_next_set_size(), true);
404        assert_eq!(combos.positions, vec![0, 1]);
405        combos.positions[0] = 5;
406        combos.positions[1] = 2;
407        assert_eq!(combos.move_to_next_set_size(), true);
408        assert_eq!(combos.positions, vec![0, 1, 2]);
409        combos.positions[0] = 3;
410        combos.positions[1] = 7;
411        combos.positions[2] = 1;
412        assert_eq!(combos.move_to_next_set_size(), true);
413        assert_eq!(combos.positions, vec![0, 1, 2, 3]);
414        combos.positions[0] = 0;
415        combos.positions[1] = 0;
416        combos.positions[2] = 0;
417        combos.positions[2] = 0;
418        assert_eq!(combos.move_to_next_set_size(), false);
419    }
420
421    #[test]
422    fn test_combinations_w_rep_move_to_next_set_size() {
423        let mut combos = CombinationsWithReplacement::all(Vec::<i64>::new());
424        assert_eq!(combos.positions, Vec::new());
425        assert_eq!(combos.move_to_next_set_size(), false);
426        let mut combos = CombinationsWithReplacement::all(vec![1]);
427        assert_eq!(combos.positions, Vec::new());
428        assert_eq!(combos.move_to_next_set_size(), true);
429        assert_eq!(combos.positions, vec![0]);
430        assert_eq!(combos.move_to_next_set_size(), false);
431        let mut combos = CombinationsWithReplacement::all(vec![1, 2, 3, 4]);
432        assert_eq!(combos.positions, Vec::new());
433        assert_eq!(combos.move_to_next_set_size(), true);
434        assert_eq!(combos.positions, vec![0]);
435        combos.positions[0] = 4;
436        assert_eq!(combos.move_to_next_set_size(), true);
437        assert_eq!(combos.positions, vec![0; 2]);
438        combos.positions[0] = 5;
439        combos.positions[1] = 2;
440        assert_eq!(combos.move_to_next_set_size(), true);
441        assert_eq!(combos.positions, vec![0; 3]);
442        combos.positions[0] = 3;
443        combos.positions[1] = 7;
444        combos.positions[2] = 1;
445        assert_eq!(combos.move_to_next_set_size(), true);
446        assert_eq!(combos.positions, vec![0; 4]);
447        combos.positions[0] = 0;
448        combos.positions[1] = 0;
449        combos.positions[2] = 0;
450        combos.positions[2] = 0;
451        assert_eq!(combos.move_to_next_set_size(), false);
452    }
453
454    #[test]
455    fn test_combinations_move_to_next_position() {
456        let mut combos = Combinations::of_size(Vec::<i64>::new(), 1);
457        assert_eq!(combos.positions, vec![0]);
458        assert_eq!(combos.move_to_next_position(), false);
459        let mut combos = Combinations::of_size(vec![1], 1);
460        assert_eq!(combos.positions, vec![0]);
461        assert_eq!(combos.move_to_next_position(), false);
462        let mut combos = Combinations::of_size(BTreeSet::from([1, 2, 3, 4]), 2);
463        assert_eq!(combos.positions, vec![0, 1]);
464        assert_eq!(combos.move_to_next_position(), true);
465        assert_eq!(combos.positions, vec![0, 2]);
466        assert_eq!(combos.move_to_next_position(), true);
467        assert_eq!(combos.positions, vec![0, 3]);
468        assert_eq!(combos.move_to_next_position(), true);
469        assert_eq!(combos.positions, vec![1, 2]);
470        assert_eq!(combos.move_to_next_position(), true);
471        assert_eq!(combos.positions, vec![1, 3]);
472        assert_eq!(combos.move_to_next_position(), true);
473        assert_eq!(combos.positions, vec![2, 3]);
474        assert_eq!(combos.move_to_next_position(), false);
475        let mut combos = Combinations::of_size("abcd".chars(), 3);
476        assert_eq!(combos.positions, vec![0, 1, 2]);
477        assert_eq!(combos.move_to_next_position(), true);
478        assert_eq!(combos.positions, vec![0, 1, 3]);
479        assert_eq!(combos.move_to_next_position(), true);
480        assert_eq!(combos.positions, vec![0, 2, 3]);
481        assert_eq!(combos.move_to_next_position(), true);
482        assert_eq!(combos.positions, vec![1, 2, 3]);
483        assert_eq!(combos.move_to_next_position(), false);
484    }
485
486    #[test]
487    fn test_combinations_w_rep_move_to_next_position() {
488        let mut combos = CombinationsWithReplacement::of_size(Vec::<i64>::new(), 1);
489        assert_eq!(combos.positions, vec![0]);
490        assert_eq!(combos.move_to_next_position(), false);
491        let mut combos = CombinationsWithReplacement::of_size(vec![1], 1);
492        assert_eq!(combos.positions, vec![0]);
493        assert_eq!(combos.move_to_next_position(), false);
494        let mut combos = CombinationsWithReplacement::of_size(BTreeSet::from([1, 2, 3, 4]), 2);
495        assert_eq!(combos.positions, vec![0, 0]);
496        assert_eq!(combos.move_to_next_position(), true);
497        assert_eq!(combos.positions, vec![0, 1]);
498        assert_eq!(combos.move_to_next_position(), true);
499        assert_eq!(combos.positions, vec![0, 2]);
500        assert_eq!(combos.move_to_next_position(), true);
501        assert_eq!(combos.positions, vec![0, 3]);
502        assert_eq!(combos.move_to_next_position(), true);
503        assert_eq!(combos.positions, vec![1, 1]);
504        assert_eq!(combos.move_to_next_position(), true);
505        assert_eq!(combos.positions, vec![1, 2]);
506        assert_eq!(combos.move_to_next_position(), true);
507        assert_eq!(combos.positions, vec![1, 3]);
508        assert_eq!(combos.move_to_next_position(), true);
509        assert_eq!(combos.positions, vec![2, 2]);
510        assert_eq!(combos.move_to_next_position(), true);
511        assert_eq!(combos.positions, vec![2, 3]);
512        assert_eq!(combos.move_to_next_position(), true);
513        assert_eq!(combos.positions, vec![3, 3]);
514        assert_eq!(combos.move_to_next_position(), false);
515        let mut combos = CombinationsWithReplacement::of_size("abcd".chars(), 3);
516        assert_eq!(combos.positions, vec![0, 0, 0]);
517        assert_eq!(combos.move_to_next_position(), true);
518        assert_eq!(combos.positions, vec![0, 0, 1]);
519        assert_eq!(combos.move_to_next_position(), true);
520        assert_eq!(combos.positions, vec![0, 0, 2]);
521        assert_eq!(combos.move_to_next_position(), true);
522        assert_eq!(combos.positions, vec![0, 0, 3]);
523        assert_eq!(combos.move_to_next_position(), true);
524        assert_eq!(combos.positions, vec![0, 1, 1]);
525        assert_eq!(combos.move_to_next_position(), true);
526        assert_eq!(combos.positions, vec![0, 1, 2]);
527        assert_eq!(combos.move_to_next_position(), true);
528        assert_eq!(combos.positions, vec![0, 1, 3]);
529        assert_eq!(combos.move_to_next_position(), true);
530        assert_eq!(combos.positions, vec![0, 2, 2]);
531        assert_eq!(combos.move_to_next_position(), true);
532        assert_eq!(combos.positions, vec![0, 2, 3]);
533        assert_eq!(combos.move_to_next_position(), true);
534        assert_eq!(combos.positions, vec![0, 3, 3]);
535        assert_eq!(combos.move_to_next_position(), true);
536        assert_eq!(combos.positions, vec![1, 1, 1]);
537        assert_eq!(combos.move_to_next_position(), true);
538        assert_eq!(combos.positions, vec![1, 1, 2]);
539        assert_eq!(combos.move_to_next_position(), true);
540        assert_eq!(combos.positions, vec![1, 1, 3]);
541        assert_eq!(combos.move_to_next_position(), true);
542        assert_eq!(combos.positions, vec![1, 2, 2]);
543        assert_eq!(combos.move_to_next_position(), true);
544        assert_eq!(combos.positions, vec![1, 2, 3]);
545        assert_eq!(combos.move_to_next_position(), true);
546        assert_eq!(combos.positions, vec![1, 3, 3]);
547        assert_eq!(combos.move_to_next_position(), true);
548        assert_eq!(combos.positions, vec![2, 2, 2]);
549        assert_eq!(combos.move_to_next_position(), true);
550        assert_eq!(combos.positions, vec![2, 2, 3]);
551        assert_eq!(combos.move_to_next_position(), true);
552        assert_eq!(combos.positions, vec![2, 3, 3]);
553        assert_eq!(combos.move_to_next_position(), true);
554        assert_eq!(combos.positions, vec![3, 3, 3]);
555        assert_eq!(combos.move_to_next_position(), false);
556    }
557
558    #[test]
559    fn test_combinations_get_current_combination() {
560        let mut combos = Combinations::of_size(vec![1, 1, 2, 3, 5, 8], 3);
561        assert_eq!(combos.get_current_combination(), Some(vec![1, 2, 3]));
562        assert_eq!(combos.move_to_next_position(), true);
563        assert_eq!(combos.get_current_combination(), Some(vec![1, 2, 5]));
564        assert_eq!(combos.move_to_next_position(), true);
565        assert_eq!(combos.get_current_combination(), Some(vec![1, 2, 8]));
566        assert_eq!(combos.move_to_next_position(), true);
567        assert_eq!(combos.get_current_combination(), Some(vec![1, 3, 5]));
568        assert_eq!(combos.move_to_next_position(), true);
569        assert_eq!(combos.get_current_combination(), Some(vec![1, 3, 8]));
570        assert_eq!(combos.move_to_next_position(), true);
571        assert_eq!(combos.get_current_combination(), Some(vec![1, 5, 8]));
572        assert_eq!(combos.move_to_next_position(), true);
573        assert_eq!(combos.get_current_combination(), Some(vec![2, 3, 5]));
574        assert_eq!(combos.move_to_next_position(), true);
575        assert_eq!(combos.get_current_combination(), Some(vec![2, 3, 8]));
576        assert_eq!(combos.move_to_next_position(), true);
577        assert_eq!(combos.get_current_combination(), Some(vec![2, 5, 8]));
578        assert_eq!(combos.move_to_next_position(), true);
579        assert_eq!(combos.get_current_combination(), Some(vec![3, 5, 8]));
580        assert_eq!(combos.move_to_next_position(), false);
581        combos.done = true;
582        assert_eq!(combos.get_current_combination(), None);
583    }
584
585    #[test]
586    fn test_combinations_w_rep_get_current_combination() {
587        let mut combos = CombinationsWithReplacement::of_size(vec![1, 1, 2, 3, 5, 8], 3);
588        assert_eq!(combos.get_current_combination(), Some(vec![1, 1, 1]));
589        assert_eq!(combos.move_to_next_position(), true);
590        assert_eq!(combos.get_current_combination(), Some(vec![1, 1, 2]));
591        assert_eq!(combos.move_to_next_position(), true);
592        assert_eq!(combos.get_current_combination(), Some(vec![1, 1, 3]));
593        assert_eq!(combos.move_to_next_position(), true);
594        assert_eq!(combos.get_current_combination(), Some(vec![1, 1, 5]));
595        assert_eq!(combos.move_to_next_position(), true);
596        assert_eq!(combos.get_current_combination(), Some(vec![1, 1, 8]));
597        assert_eq!(combos.move_to_next_position(), true);
598        assert_eq!(combos.get_current_combination(), Some(vec![1, 2, 2]));
599        assert_eq!(combos.move_to_next_position(), true);
600        assert_eq!(combos.get_current_combination(), Some(vec![1, 2, 3]));
601        assert_eq!(combos.move_to_next_position(), true);
602        assert_eq!(combos.get_current_combination(), Some(vec![1, 2, 5]));
603        assert_eq!(combos.move_to_next_position(), true);
604        assert_eq!(combos.get_current_combination(), Some(vec![1, 2, 8]));
605        assert_eq!(combos.move_to_next_position(), true);
606        assert_eq!(combos.get_current_combination(), Some(vec![1, 3, 3]));
607        assert_eq!(combos.move_to_next_position(), true);
608        assert_eq!(combos.get_current_combination(), Some(vec![1, 3, 5]));
609        assert_eq!(combos.move_to_next_position(), true);
610        assert_eq!(combos.get_current_combination(), Some(vec![1, 3, 8]));
611        assert_eq!(combos.move_to_next_position(), true);
612        assert_eq!(combos.get_current_combination(), Some(vec![1, 5, 5]));
613        assert_eq!(combos.move_to_next_position(), true);
614        assert_eq!(combos.get_current_combination(), Some(vec![1, 5, 8]));
615        assert_eq!(combos.move_to_next_position(), true);
616        assert_eq!(combos.get_current_combination(), Some(vec![1, 8, 8]));
617        assert_eq!(combos.move_to_next_position(), true);
618        assert_eq!(combos.get_current_combination(), Some(vec![2, 2, 2]));
619        assert_eq!(combos.move_to_next_position(), true);
620        assert_eq!(combos.get_current_combination(), Some(vec![2, 2, 3]));
621        assert_eq!(combos.move_to_next_position(), true);
622        assert_eq!(combos.get_current_combination(), Some(vec![2, 2, 5]));
623        assert_eq!(combos.move_to_next_position(), true);
624        assert_eq!(combos.get_current_combination(), Some(vec![2, 2, 8]));
625        assert_eq!(combos.move_to_next_position(), true);
626        assert_eq!(combos.get_current_combination(), Some(vec![2, 3, 3]));
627        assert_eq!(combos.move_to_next_position(), true);
628        assert_eq!(combos.get_current_combination(), Some(vec![2, 3, 5]));
629        assert_eq!(combos.move_to_next_position(), true);
630        assert_eq!(combos.get_current_combination(), Some(vec![2, 3, 8]));
631        assert_eq!(combos.move_to_next_position(), true);
632        assert_eq!(combos.get_current_combination(), Some(vec![2, 5, 5]));
633        assert_eq!(combos.move_to_next_position(), true);
634        assert_eq!(combos.get_current_combination(), Some(vec![2, 5, 8]));
635        assert_eq!(combos.move_to_next_position(), true);
636        assert_eq!(combos.get_current_combination(), Some(vec![2, 8, 8]));
637        assert_eq!(combos.move_to_next_position(), true);
638        assert_eq!(combos.get_current_combination(), Some(vec![3, 3, 3]));
639        assert_eq!(combos.move_to_next_position(), true);
640        assert_eq!(combos.get_current_combination(), Some(vec![3, 3, 5]));
641        assert_eq!(combos.move_to_next_position(), true);
642        assert_eq!(combos.get_current_combination(), Some(vec![3, 3, 8]));
643        assert_eq!(combos.move_to_next_position(), true);
644        assert_eq!(combos.get_current_combination(), Some(vec![3, 5, 5]));
645        assert_eq!(combos.move_to_next_position(), true);
646        assert_eq!(combos.get_current_combination(), Some(vec![3, 5, 8]));
647        assert_eq!(combos.move_to_next_position(), true);
648        assert_eq!(combos.get_current_combination(), Some(vec![3, 8, 8]));
649        assert_eq!(combos.move_to_next_position(), true);
650        assert_eq!(combos.get_current_combination(), Some(vec![5, 5, 5]));
651        assert_eq!(combos.move_to_next_position(), true);
652        assert_eq!(combos.get_current_combination(), Some(vec![5, 5, 8]));
653        assert_eq!(combos.move_to_next_position(), true);
654        assert_eq!(combos.get_current_combination(), Some(vec![5, 8, 8]));
655        assert_eq!(combos.move_to_next_position(), true);
656        assert_eq!(combos.get_current_combination(), Some(vec![8, 8, 8]));
657        assert_eq!(combos.move_to_next_position(), false);
658        combos.done = true;
659        assert_eq!(combos.get_current_combination(), None);
660    }
661}
combinatorial/combinations.rs

combinatorial/
combinations.rs
