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
use std::iter::FromIterator;
pub struct Permutations<T> {
items: Vec<T>,
size: usize,
stack: Vec<usize>,
index: usize,
started: bool,
}
impl<T> Permutations<T> {
pub fn new(items: Vec<T>) -> Permutations<T> {
let size = items.len();
Permutations {
items,
size,
stack: vec![0; size],
index: 0,
started: false,
}
}
}
impl<T> FromIterator<T> for Permutations<T> {
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
Self::new(Vec::from_iter(iter))
}
}
impl<T: Clone> Iterator for Permutations<T> {
type Item = Vec<T>;
fn next(&mut self) -> Option<Vec<T>> {
if self.started {
while self.index < self.size {
if self.stack[self.index] < self.index {
if self.index % 2 == 0 {
self.items.swap(0, self.index);
} else {
self.items.swap(self.stack[self.index], self.index);
}
self.stack[self.index] += 1;
self.index = 0;
return Some(self.items.clone());
} else {
self.stack[self.index] = 0;
self.index += 1;
}
}
None
} else {
self.started = true;
Some(self.items.clone())
}
}
}
#[cfg(test)]
mod tests {
use std::collections::HashSet;
use super::*;
#[test]
fn test_permutations_of_list_with_size_3() {
let mut permutations: HashSet<Vec<u8>> = HashSet::new();
for permutation in Permutations::new(vec![1, 2, 3]) {
permutations.insert(permutation.clone());
assert_eq!(permutation.len(), 3);
assert!(permutation.contains(&1));
assert!(permutation.contains(&2));
assert!(permutation.contains(&3));
}
assert_eq!(permutations.len(), 6);
}
#[test]
fn test_permutations_of_list_with_size_5() {
let mut permutations: HashSet<Vec<u8>> = HashSet::new();
for permutation in (0..5).collect::<Permutations<u8>>() {
permutations.insert(permutation.clone());
assert_eq!(permutation.len(), 5);
assert!(permutation.contains(&0));
assert!(permutation.contains(&1));
assert!(permutation.contains(&2));
assert!(permutation.contains(&3));
assert!(permutation.contains(&4));
}
assert_eq!(permutations.len(), 120);
}
}