Permutations by swapping: Difference between revisions
Added Rust solution
Drkameleon (talk | contribs) (Added Arturo implementation) |
(Added Rust solution) |
||
Line 2,797:
Perm: [2, 1, 4, 3] Sign: 1
Perm: [2, 1, 3, 4] Sign: -1
</pre>
=={{header|Rust}}==
<lang rust>// Implementation of Heap's algorithm.
// See https://en.wikipedia.org/wiki/Heap%27s_algorithm#Details_of_the_algorithm
fn generate<T, F>(a: &mut [T], mut output: F)
where
F: FnMut(&[T]),
{
let n = a.len();
let mut c = vec![0; n];
let mut i = 1;
output(a);
while i < n {
if c[i] < i {
if (i & 1) == 0 {
a.swap(0, i);
} else {
a.swap(c[i], i);
}
output(a);
c[i] += 1;
i = 1;
} else {
c[i] = 0;
i += 1;
}
}
}
fn print_permutations<T: std::fmt::Debug>(a: &mut [T]) {
let mut even = true;
let p = move |x: &[T]| {
println!("{:?} {}", x, if even { "+1" } else { "-1" });
even = !even;
};
generate(a, p);
}
fn main() {
println!("Permutations and signs for three items:");
let mut a = vec![0, 1, 2];
print_permutations(&mut a);
println!("\nPermutations and signs for four items:");
let mut b = vec![0, 1, 2, 3];
print_permutations(&mut b);
}</lang>
{{out}}
<pre>
Permutations and signs for three items:
[0, 1, 2] +1
[1, 0, 2] -1
[2, 0, 1] +1
[0, 2, 1] -1
[1, 2, 0] +1
[2, 1, 0] -1
Permutations and signs for four items:
[0, 1, 2, 3] +1
[1, 0, 2, 3] -1
[2, 0, 1, 3] +1
[0, 2, 1, 3] -1
[1, 2, 0, 3] +1
[2, 1, 0, 3] -1
[3, 1, 0, 2] +1
[1, 3, 0, 2] -1
[0, 3, 1, 2] +1
[3, 0, 1, 2] -1
[1, 0, 3, 2] +1
[0, 1, 3, 2] -1
[0, 2, 3, 1] +1
[2, 0, 3, 1] -1
[3, 0, 2, 1] +1
[0, 3, 2, 1] -1
[2, 3, 0, 1] +1
[3, 2, 0, 1] -1
[3, 2, 1, 0] +1
[2, 3, 1, 0] -1
[1, 3, 2, 0] +1
[3, 1, 2, 0] -1
[2, 1, 3, 0] +1
[1, 2, 3, 0] -1
</pre>
| |||