Heap's algorithm

Question

Trying to reproduce Heap's algorithm, for generating all possible permutations of an array of integers, but I can't solve it for other integers than three. Heap's algorithm from Wikipedia:

procedure generate(N : integer, data : array of any):
if N = 1 then
    output(data)
else
    for c := 1; c <= N; c += 1 do
        generate(N - 1, data)
        swap(data[if N is odd then 1 else c], data[N])

My code:

    public static void perm(int[] list, int n){
    if(n==1){
            System.out.println(Arrays.toString(list));
    } else {
        for(int c=1;c<=n;c++){ /for(int c=0;c<n;c++)
            perm(list,n-1);
            if(n%2==0){
                int temp1=list[c];    //This is line 17
                list[c]=list[list.length-1];
                list[list.length-1]=temp1;
             }else{
                int temp2=list[0];
                list[0]=list[list.length-1];
                list[list.length-1]=temp2;
            }
        }
    }
}

What am I doing wrong and misunderstanding about it? Why does it Only work with [1,2,3] (n=3) as input and neither with n=2 nor n=4?

Runs:

perm(A,3);
[1, 2, 3]
[1, 3, 2]
[2, 3, 1]
[2, 1, 3]
[3, 1, 2]
[3, 2, 1]

perm(A,4)
[1, 2, 3, 4]
[1, 4, 3, 2]
.
.
.
[2, 4, 1, 3]
[2, 3, 1, 4]
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
at Permutation.perm(Permutation.java:17)
at Permutation.main(Permutation.java:43)

Thanks for the replies but that cannot be the problem. I tried changing that before I asked the question but think starting from 1 is part of the algorithm if I understand the Wiki-page correctly as it is explicitly stated (even though no particular language/for-loop-scheme is mentioned). Below is an output for n=4 which contains several duplicates. Link to Wiki-page: http://en.wikipedia.org/wiki/Heap%27s_algorithm

[1, 2, 3, 4]
[4, 2, 3, 1]
[2, 1, 3, 4]
[4, 1, 3, 2]
[1, 2, 3, 4]
[4, 2, 3, 1]
[4, 1, 3, 2]
[2, 1, 3, 4]
[1, 4, 3, 2]
[2, 4, 3, 1]
[4, 1, 3, 2]
[2, 1, 3, 4]
[1, 2, 3, 4]
[4, 2, 3, 1]
[2, 1, 3, 4]
[4, 1, 3, 2]
[1, 2, 3, 4]
[4, 2, 3, 1]
[2, 1, 4, 3]
[3, 1, 4, 2]
[1, 2, 4, 3]
[3, 2, 4, 1]
[2, 1, 4, 3]
[3, 1, 4, 2]

Collocate

possible duplicate of Heap's algorithm permutation generator – Lysol

Better late than never, I suppose. The bug in the wikipedia article and a fix (in Python, plus pseudocode) are explored in the linked question. – Lysol

Answer 1

Try this:

//Heap's Algorithm
public static void perm(int[] list, int n)
{
    if(n == 1)
    {
        System.out.println(Arrays.toString(list));
    } 
    else 
    {
        for(int i=0; i<n; i++)
        {
            perm(list,n-1);

            int j = ( n % 2 == 0 ) ? i : 0; 

            int t = list[n-1];              
            list[n-1] = list[j];
            list[j] = t;                
        }
    }
}


public static void main(String[] args) {

    int[] list = new int[]{1,2,3}; 
    perm(list, list.length);

}

You were using the length of the input list instead of "n" for your swap

Saffian

Answer 2

In most contemporary programming languages the arrays are 0 indexed and thus for(int c=1;c<=n;c++){ is not a correct cycle to iterate over the elements. The pseudo code assumes 1-indexed array.

Equatorial

Thanks for your reply but don't think that is the problem, see my edit above. – Collocate

Answer 3

Change this:

public static void perm(int[] list, int n){
    if(n==1){
            System.out.println(Arrays.toString(list));
    } else {
        for(int c=1;c<=n;c++){
            perm(list,n-1);
            if(n%2==0){
                int temp1=list[c];    //This is line 17
                list[c]=list[list.length-1];
                list[list.length-1]=temp1;
             }else{
                int temp2=list[0];
                list[0]=list[list.length-1];
                list[list.length-1]=temp2;
            }
        }
    }
}

To this:

public static void perm(int[] list, int n){
    if(n==1){
            System.out.println(Arrays.toString(list));
    } else {
        for(int c=0;c<n;c++){
            perm(list,n-1);
            if(n%2==0){
                int temp1=list[c];    //This is line 17
                list[c]=list[list.length-1];
                list[list.length-1]=temp1;
             }else{
                int temp2=list[0];
                list[0]=list[list.length-1];
                list[list.length-1]=temp2;
            }
        }
    }
}

Pouliot

Thanks for the reply but I don't think that is the problem but rather part of the algorithm. Please see my edit above. – Collocate

Answer 4

Are you sure that c is bounded above by the length of the list?

Salley

Answer 5

An array of 4 has the indexes 0, 1, 2 and 3. Java (and many other languages) start counting at 0. On line four you have the following loop:

for(int c=1;c<=n;c++){

This starts at 1 (exists), then 2 (exists), then 3 (exists), then 4 (array out of bound).

To fix, change the loop:

for(int c = 0; c < n; c++){

Crossroad