treebender/
utils.rs

1use std::error::Error;
2
3/// Boxed static error type
4pub type Err = Box<dyn Error + 'static>;
5
6/// Takes a list where each element is a set of choices, and returns all the possible sets
7/// generated. Will clone the elements.
8///
9/// ```
10/// let v = vec![
11///   vec![1],
12///   vec![2, 3],
13///   vec![4],
14///   vec![5, 6, 7],
15/// ];
16///
17/// assert_eq!(treebender::utils::combinations(&v), vec![
18///   vec![1, 2, 4, 5],
19///   vec![1, 3, 4, 5],
20///   vec![1, 2, 4, 6],
21///   vec![1, 3, 4, 6],
22///   vec![1, 2, 4, 7],
23///   vec![1, 3, 4, 7],
24/// ]);
25/// ```
26pub fn combinations<T>(list: &[Vec<T>]) -> Vec<Vec<T>>
27where
28  T: Clone,
29{
30  if list.is_empty() {
31    Vec::new()
32  } else if list.len() == 1 {
33    list[0].iter().map(|e| vec![e.clone()]).collect()
34  } else {
35    let (head, tail) = list.split_at(1);
36    let head = &head[0];
37
38    combinations(tail)
39      .into_iter()
40      .map(|subseq| {
41        // prepend every element of the head to every possible subseq
42        head.iter().map(move |v| {
43          let mut newseq = subseq.clone();
44          newseq.insert(0, v.clone());
45          newseq
46        })
47      })
48      .flatten()
49      .collect()
50  }
51}