Task

Generate permutations of n items in which successive permutations differ from each other by the swapping of any two items.

Also generate the sign of the permutation which is +1 when the permutation is generated from an even number of swaps from the initial state, and -1 for odd.

Show the permutations and signs of three items, in order of generation here.

Such data are of use in generating the determinant of a square matrix and any functions created should bear this in mind.

Note: The Steinhaus–Johnson–Trotter algorithm generates successive permutations where adjacent items are swapped, but from this discussion adjacency is not a requirement.



References

 Steinhaus–Johnson–Trotter algorithm
 Johnson-Trotter Algorithm Listing All Permutations
 Heap's algorithm
 [1] Tintinnalogia


Related tasks

   Matrix arithmetic
   Gray code


// 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], output: F)
where
    F: Fn(&[T], isize),
{
    let n = a.len();
    let mut c = vec![0; n];
    let mut i = 1;
    let mut sign = 1;
    output(a, sign);
    while i < n {
        if c[i] < i {
            if (i & 1) == 0 {
                a.swap(0, i);
            } else {
                a.swap(c[i], i);
            }
            sign = -sign;
            output(a, sign);
            c[i] += 1;
            i = 1;
        } else {
            c[i] = 0;
            i += 1;
        }
    }
}
 
fn print_permutation<T: std::fmt::Debug>(a: &[T], sign: isize) {
    println!("{:?} {}", a, sign);
}
 
fn main() {
    println!("Permutations and signs for three items:");
    let mut a = vec![0, 1, 2];
    generate(&mut a, print_permutation);
 
    println!("\nPermutations and signs for four items:");
    let mut b = vec![0, 1, 2, 3];
    generate(&mut b, print_permutation);
}