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]

possible duplicate of Heap's algorithm permutation generator — rici
– rici, Commented Mar 14, 2015 at 17:38
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. — rici
– rici, Commented Mar 14, 2015 at 17:39

brunoma · Accepted Answer · 2015-01-16 18:45:06Z

3

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

answered Jan 16, 2015 at 18:45

brunoma

535 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ivaylo Strandjev · Accepted Answer · 2014-07-22 13:50:10Z

1

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.

answered Jul 22, 2014 at 13:50

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

1 Comment

user2069136 Over a year ago

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

Eddie Martinez · Accepted Answer · 2014-07-22 13:52:25Z

1

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;
            }
        }
    }
}

answered Jul 22, 2014 at 13:52

Eddie Martinez

13.9k15 gold badges86 silver badges109 bronze badges

2 Comments

user2069136 Over a year ago

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

Erk Aug 28 at 2:09

I think it's supposed to be swapped on n-1 not the list.length-1

Benjamin Kovach · Accepted Answer · 2014-07-22 13:50:15Z

0

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

answered Jul 22, 2014 at 13:50

Benjamin Kovach

3,2812 gold badges27 silver badges39 bronze badges

Comments

Cheiron · Accepted Answer · 2014-07-22 13:51:03Z

0

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++){

answered Jul 22, 2014 at 13:51

Cheiron

3,7464 gold badges34 silver badges66 bronze badges

Collectives™ on Stack Overflow

Heap's algorithm

5 Answers 5

Comments

1 Comment

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

1 Comment

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related