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

#[derive(Debug)]
pub struct Permutator<I> {
    original_producer: I,
    current_producers: Vec<I>,
    root: String,
}

impl<I: Iterator + Clone> Permutator<I> {
    pub fn new(producer: I) -> Self {
        Self {
            original_producer: producer.clone(),
            current_producers: vec![producer],
            root: String::new(),
        }
    }

    fn new_producer(&self) -> I {
        self.original_producer.clone()
    }
}

impl<I: Iterator<Item=char> + Clone> Iterator for Permutator<I> {
    type Item = String;

    fn next(&mut self) -> Option<String> {
        let next_char = self.current_producers.last_mut()
            .and_then(|producer| producer.next());

        if let Some(value) = next_char {
            let mut string = self.root.clone();
            string.push(value);
            Some(string)

        } else {
            let mut count_pop = 1;
            self.current_producers.pop();

            while let Some(previous_producer) = self.current_producers.last_mut() {
                if let Some(next_root_char) = previous_producer.next() {
                    self.root.pop();
                    self.root.push(next_root_char);
                    count_pop -= 1;
                    break;
                } else {
                    self.root.pop();
                    self.current_producers.pop();
                    count_pop += 1;
                }
            }

            for _ in 0..count_pop {
                let mut new_producer = self.new_producer();
                self.root.push(new_producer.next().unwrap());
                self.current_producers.push(new_producer);
            }

            self.current_producers.push(self.original_producer.clone());

            self.next()
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use std::convert::TryInto;

    #[test]
    fn produce_all_permutations_with_single_char() {
        let mut permutate = Permutator::new("ab".chars());

        assert_eq!(permutate.next().unwrap(), "a");
        assert_eq!(permutate.next().unwrap(), "b");
    }

    #[test]
    fn produce_all_permutations_with_two_chars() {
        let mut permutate = Permutator::new("ab".chars());

        assert_eq!(permutate.next().unwrap(), "a");
        assert_eq!(permutate.next().unwrap(), "b");
        assert_eq!(permutate.next().unwrap(), "aa");
        assert_eq!(permutate.next().unwrap(), "ab");
        assert_eq!(permutate.next().unwrap(), "ba");
        assert_eq!(permutate.next().unwrap(), "bb");
    }

    #[test]
    fn produce_all_permutations_with_three_chars() {
        let mut permutate = Permutator::new("ab".chars());

        for _ in 0..2 + 2^2 {
            permutate.next();
        }

        assert_eq!(permutate.next().unwrap(), "aaa");
        assert_eq!(permutate.next().unwrap(), "aab");
        assert_eq!(permutate.next().unwrap(), "aba");
        assert_eq!(permutate.next().unwrap(), "abb");
        assert_eq!(permutate.next().unwrap(), "baa");
        assert_eq!(permutate.next().unwrap(), "bab");
        assert_eq!(permutate.next().unwrap(), "bba");
        assert_eq!(permutate.next().unwrap(), "bbb");
    }

    #[test]
    fn produce_only_first_char_permutations() {
        let char_set = "01";
        let set_length = char_set.len();

        let mut permutate = Permutator::new(char_set.chars());

        for length in 1..9 {
            assert_eq!(permutate.next().unwrap(), char_set[0..1].repeat(length));

            for _ in 0..set_length.pow(length.try_into().unwrap()) - 1 {
                assert!(permutate.next().is_some());
            }
        }
    }
}