rust_combinatorics 0.0.1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

pub struct Choose<T: Copy> {
    vec: Vec<T>,
    k: usize,
    indices: Vec<usize>,
    first: bool,
}

impl<T: Copy> Choose<T> {
    fn new(vec: Vec<T>, k: usize) -> Choose<T> {
        Choose { vec: vec,
                 k: k,
                 indices: range(0, k).collect(),
                 first: true,
        }
    }

    fn n(&self) -> usize {
        self.vec.len()
    }
}

impl<T: Copy> Iterator for Choose<T> {
    type Item = Vec<T>;

    fn next(&mut self) -> Option<Vec<T>> {
        match self.first {
            true => {
                match self.n() < self.k {
                    true => None,
                    false => {
                        self.first = false;
                        Some(self.indices.iter().map(|&i| *self.vec.get(i).unwrap()).collect())
                    }
                }
            },
            false => {
                let first_thing = range(0, self.k).rev().filter(|&_i| *self.indices.get(_i).unwrap() != _i + self.n() - self.k).take(1).collect::<Vec<usize>>();
                match first_thing.len() {
                    0 => None,
                    _ => {
                        let i = first_thing[0];
                        self.indices[i] += 1;
                        for j in range(i+1, self.k) {
                            self.indices[j] = self.indices[j-1] + 1;
                        }
                        Some(self.indices.iter().map(|&i| *self.vec.get(i).unwrap()).collect())
                    }
                }
            }
        }
    }
}

pub trait Chooseable<T> {
    fn choose(self, k: usize) -> Choose<T>;
}

impl<T: Copy> Chooseable<T> for Vec<T> {
    fn choose(self, k: usize) -> Choose<T> {
        Choose::new(self, k)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn it_returns_none_when_choosing_one_from_an_empty_list() {
        let vector: Vec<()> = vec![];
        let mut it = vector.choose(1);
        assert!(it.next().is_none());
    }

    #[test] fn it_returns_the_empty_vector_when_choosing_zero_from_an_empty_list() {
        let vector: Vec<()> = vec![];
        let mut it = vector.choose(0);
        assert_eq!(it.next().unwrap(), vec![]);
        assert!(it.next().is_none());
    }

    #[test] fn it_returns_the_empty_vector_when_choosing_zero_from_a_list_with_elements() {
        let vector = vec![0, 1, 2];
        let mut it = vector.choose(0);
        assert_eq!(it.next().unwrap().len(), 0);
        assert!(it.next().is_none());
    }

    #[test] fn it_returns_each_item_when_choosing_one_from_a_list_with_items() {
        let vector = vec![0, 1, 2];
        let mut it = vector.choose(1);

        assert_eq!(it.next().unwrap(), vec![0]);
        assert_eq!(it.next().unwrap(), vec![1]);
        assert_eq!(it.next().unwrap(), vec![2]);
        assert!(it.next().is_none());
    }

    #[test] fn it_returns_each_item_combination_when_choosing_two_from_a_list_with_items() {
        let vector = vec![0, 1, 2];
        let mut it = vector.choose(2);

        assert_eq!(it.next().unwrap(), vec![0, 1]);
        assert_eq!(it.next().unwrap(), vec![0, 2]);
        assert_eq!(it.next().unwrap(), vec![1, 2]);
        assert!(it.next().is_none());
    }

    #[test] fn it_returns_each_item_combination_when_choosing_three_from_a_list_with_four_items() {
        let vector = vec![0, 1, 2, 3, 4];
        let mut it = vector.choose(2);

        assert_eq!(it.next().unwrap(), vec![0, 1]);
        assert_eq!(it.next().unwrap(), vec![0, 2]);
        assert_eq!(it.next().unwrap(), vec![0, 3]);
        assert_eq!(it.next().unwrap(), vec![0, 4]);
        assert_eq!(it.next().unwrap(), vec![1, 2]);
        assert_eq!(it.next().unwrap(), vec![1, 3]);
        assert_eq!(it.next().unwrap(), vec![1, 4]);
        assert_eq!(it.next().unwrap(), vec![2, 3]);
        assert_eq!(it.next().unwrap(), vec![2, 4]);
        assert_eq!(it.next().unwrap(), vec![3, 4]);
        assert!(it.next().is_none());
    }
}