Anonymous user
Permutations: Difference between revisions
→{{header|Rust}}: Added Rust
(added FreeBASIC) |
(→{{header|Rust}}: Added Rust) |
||
Line 4,646:
heoll
helol</pre>
=={{header|Rust}}==
===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.
<lang rust>struct QuickPerm<T> {
idxs: Vec<usize>,
elems: Vec<T>,
idx: usize,
}
impl<T: Clone> QuickPerm<T> {
fn new(elems: Vec<T>) -> Self {
QuickPerm { idxs: (0..elems.len()+1).collect(), elems: elems, idx: 1 }
}
}
impl<T: Clone> Iterator for QuickPerm<T> {
type Item = Vec<T>;
fn next(&mut self) -> Option<Self::Item> {
if self.idx == self.elems.len() { return None; }
self.idxs[self.idx] -= 1;
let other = if self.idx % 2 == 1 { self.idxs[self.idx] } else { 0 };
self.elems.swap(self.idx, other);
self.idx = 1;
while self.idxs[self.idx] == 0 {
self.idxs[self.idx] = self.idx;
self.idx += 1;
}
Some(self.elems.clone())
}
}
fn main() {
for perm in QuickPerm::new(vec![1,2,3]) {
println!("{:?}", perm);
}
}</lang>
===Recursive===
<lang rust>use std::collections::VecDeque;
fn permute<T, F: Fn(&[T])>(used: &mut Vec<T>, unused: &mut VecDeque<T>, action: &F) {
if unused.is_empty() {
action(used);
} else {
for _ in 0..unused.len() {
used.push(unused.pop_front().unwrap());
permute(used, unused, action);
unused.push_back(used.pop().unwrap());
}
}
}
// Same as the vec! macro, but for VecDeques as well
macro_rules! vec_deque {
($($item:expr),*) => {{
let mut deque = ::std::collections::VecDeque::new();
$(deque.push_back($item);)*
deque
}}
}
fn main() {
permute(&mut Vec::new(), &mut vec_deque![1,2,3], &|perm| println!("{:?}", perm));
}</lang>
=={{header|SAS}}==
| |||