41 lines
993 B
Rust
41 lines
993 B
Rust
pub fn permutations(size: usize) -> Permutations {
|
|
Permutations { idxs: (0..size).collect(), swaps: vec![0; size], i: 0 }
|
|
}
|
|
|
|
pub struct Permutations {
|
|
idxs: Vec<usize>,
|
|
swaps: Vec<usize>,
|
|
i: usize,
|
|
}
|
|
|
|
impl Iterator for Permutations {
|
|
type Item = Vec<usize>;
|
|
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
if self.i > 0 {
|
|
loop {
|
|
if self.i >= self.swaps.len() { return None; }
|
|
if self.swaps[self.i] < self.i { break; }
|
|
self.swaps[self.i] = 0;
|
|
self.i += 1;
|
|
}
|
|
self.idxs.swap(self.i, (self.i & 1) * self.swaps[self.i]);
|
|
self.swaps[self.i] += 1;
|
|
}
|
|
self.i = 1;
|
|
Some(self.idxs.clone())
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
let perms = permutations(3).collect::<Vec<_>>();
|
|
assert_eq!(perms, vec![
|
|
vec![0, 1, 2],
|
|
vec![1, 0, 2],
|
|
vec![2, 0, 1],
|
|
vec![0, 2, 1],
|
|
vec![1, 2, 0],
|
|
vec![2, 1, 0],
|
|
]);
|
|
}
|