Heap's algorithm incomplete

help
1

I'm trying to implement Heap's algorithm in rust and am struggling to do so. I'm essentially trying to port the example from this blog.

 

fn swap(mut v: Vec<usize>, i: usize, j: usize) -> Vec<usize> {
    let t = v[i];
    v[i] = v[j];
    v[j] = t;
    v
}

fn heaps_alg(mut v: Vec<usize>, n: usize) -> Option<Vec<usize>> {
    
    if n == 1 {
        println!("Permution complete: {:?}", v);
        Some(v.clone());
    }
    for i in 0..n {
        heaps_alg(v.clone(), n-1);
        let j = {if n % 2 == 0 { i } else { 0 } };
        if n - 1 == j { continue } else {
        v = swap(v.clone(), n-1, j);
        
        }
    }
    None
    
}

fn main() {
    heaps_alg(vec![1,2,3], 3);
}

(Playground)

Output:

Permution complete: [1, 2, 3]
Permution complete: [2, 1, 3]
Permution complete: [3, 2, 1]
Permution complete: [2, 3, 1]
Permution complete: [1, 2, 3]
Permution complete: [2, 1, 3]

As you can see, the number of permutations is correct, but there are duplicates leading to an incomplete collection of permutations. It seems my algorithm is not performing the swap correctly. Any suggestions or help in troubleshooting?

2

Hi, I think the blog post has an error in their algorithm. Heap's is supposed to use exactly 1 swap between each permutation.

Maybe we don't need to blame the blog - this is an error that the Wikipedia article for the algorithm carried for a while, but it should since have been fixed (no guarantees it's not broken again in a new way :slightly_smiling_face: ).

3

The blog mentions the wikipedia bug and says the algorithm presented in the blog post is the corrected version:

    public void heaps_algorithm(int[] a, int n) {
        if(n == 1) {
            // (got a new permutation)
            System.out.println(Arrays.toString(a));
            return;
        }
        for(int i = 0;i > (n - 1);i++) {
            heaps_algorithm(a, n-1);
            // always swap the first when odd,
            // swap the i-th when even
            if(n % 2 == 0) swap(a, n-1, i);
            else swap(a, n-1, 0);
        }
        heaps_algorithm(a, n-1);
    }

That seems to use a single swap for each iteration of the recursion.

1 Like
4

If you wanted to follow that to the letter, it’d be something like this:

fn heaps_alg(v: &mut [i32], n: usize) {
    if n == 1 {
        println!("{:?}", v);
        return;
    }

    for x in 0..n - 1 {
        heaps_alg(v, n - 1);
        if n % 2 == 0 {
            v.swap(n - 1, x);
        } else {
            v.swap(n - 1, 0);
        }
    }
    heaps_alg(v, n - 1);
}

fn main() {
    heaps_alg(&mut vec![1, 2, 3], 3);
}
1 Like
5

The difference is that it needs to modify the vector in place to keep that progress for the further swaps. And return directly after producing a permutation. Like @vitalyd did. playground link

It's nice to use the Vec/slice .swap(i, j) method here.

Edit: It is left unsolved how to send the generated swaps "out" — either using a callback or pushing to a vector come to mind. If we had generators - unstable Rust - we could use that!

1 Like
6

You can just turn it into an iterator and put the actual logic inside its next() method.

1 Like
7

I'm not smart enough to follow what you mean. Does "it" refer to the original collection?

8

Sorry it might have been unclear; by "it" I just meant the code that implements the algorithm.

9

Since it's a recursive algorithm (in this shape), it's not that easy to "just" turn it into an iterator. I was mentioning some approaches to output that might be compatible with the current recursive shape of it - and I think generators would be too, even though I haven't tried that out.

(By all means rewrite it as an iterator if you are interested!)

10

One of my first Rust programs was finding permutations. No idea if what I have is related to Heap's algorithm:

use std::env;

// Generate the next permutation lexicographically after a given permutation (if there is one).
fn next_permutation<T: PartialOrd + Copy>(permutation: &[T]) -> Option<Vec<T>> {
    let mut result: Vec<T> = permutation.to_vec();

    // Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation
    for w in result.windows(2).enumerate().rev() {
        let i = w.0;
        if result[i] < result[i + 1] {
            // Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
            for j in (0..permutation.len()).rev() {
                if permutation[j] > permutation[i] {
                    // Swap s[i] with s[j].
                    result.swap(i, j);

                    // Reverse the order of all of the elements after index i till the last element.
                    result[(i + 1)..].reverse();

                    return Some(result);
                }
            }
        }
    }
    None
}

fn list_permutations<T: PartialOrd + Copy>(permutation: &[T]) -> Vec<Vec<T>> {
    let mut permutation_list: Vec<Vec<T>> = vec![];
    permutation_list.push(permutation.to_vec());

    while let Some(a) = next_permutation(&permutation_list.last().unwrap().to_vec()) {
        permutation_list.push(a);
    }
    permutation_list
}

fn main() {
    let args: Vec<String> = env::args().collect();
    println!("{:?}", args);

    if args.len() < 2 {
        println!("Please give word argument");
        std::process::exit(0);
    }

    let permutation: Vec<u8> = args[1].as_bytes().to_vec();

    let permutation_list = list_permutations(&permutation);
    for permutation in permutation_list {
        println!("{}", String::from_utf8(permutation.clone()).unwrap());
    }
}

Wkipedia has a non-recursive version of Heaps' algorithm.

11

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.