Permutations: Difference between revisions
Content added Content deleted
(added FreeBASIC) |
(→{{header|Rust}}: Added Rust) |
||
Line 4,646: | Line 4,646: | ||
heoll |
heoll |
||
helol</pre> |
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}}== |
=={{header|SAS}}== |