Permutations: Difference between revisions

Content added Content deleted
m (→‎{{header|C sharp|C#}}: Eliminated method call not included in source here)
Line 4,511: Line 4,511:
=={{header|Rust}}==
=={{header|Rust}}==
===Iterative===
===Iterative===
Using the QuickPerm algorithm. This solution assumes you want seperate copies of each permutation. An in-place version is possible, but incompatible with the <code>Iterator</code> trait.
Uses Heap's algorithm. An in-place version is possible but is incompatible with <code>Iterator</code>.
<lang rust>struct QuickPerm<T> {
<lang rust>pub fn permutations(size: usize) -> Permutations {
⚫
Permutations { idxs: (0..size).collect(), swaps: vec![0; size], i: 0 }
⚫
idxs: Vec<usize>,
elems: Vec<T>,
idx: usize,
}
}


pub struct Permutations {
impl<T: Clone> QuickPerm<T> {
fn new(elems: Vec<T>) -> Self {
idxs: Vec<usize>,
⚫
swaps: Vec<usize>,
⚫
QuickPerm { idxs: (0..elems.len()+1).collect(), elems: elems, idx: 1 }
}
i: usize,
}
}


impl<T: Clone> Iterator for QuickPerm<T> {
impl Iterator for Permutations {
type Item = Vec<T>;
type Item = Vec<usize>;

fn next(&mut self) -> Option<Self::Item> {
fn next(&mut self) -> Option<Self::Item> {
if self.idx == self.elems.len() { return None; }
if self.i > 0 {
loop {

self.idxs[self.idx] -= 1;
if self.i >= self.swaps.len() { return None; }
let other = if self.idx % 2 == 1 { self.idxs[self.idx] } else { 0 };
if self.swaps[self.i] < self.i { break; }
self.elems.swap(self.idx, other);
self.swaps[self.i] = 0;
self.idx = 1;
self.i += 1;
while self.idxs[self.idx] == 0 {
}
self.idxs[self.idx] = self.idx;
self.idxs.swap(self.i, (self.i & 1) * self.swaps[self.i]);
self.idx += 1;
self.swaps[self.i] += 1;
}
}
Some(self.elems.clone())
self.i = 1;
Some(self.idxs.clone())
}
}
}
}


fn main() {
fn main() {
let perms = permutations(3).collect::<Vec<_>>();
for perm in QuickPerm::new(vec![1,2,3]) {
println!("{:?}", perm);
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],
⚫
]);
}</lang>
}</lang>


Retrieved from "https://rosettacode.org/wiki/Permutations"