Heap algorithm

Question

Trying to reproduce a heap algorithm to generate all possible permutations of an array of integers, but I can't solve it for integers other than three. Wikipedia heap algorithm:

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 is:

  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? Why does this only work with [1,2,3] (n = 3) as input and neither with n = 2 nor n = 4?

Starts up:

 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 answers, but this may not be a problem. I tried to change this before asking a question, but I think that starting with 1 is part of the algorithm, if I understand the Wiki page correctly, as it is explicitly stated (although a specific language / loop scheme is mentioned). Below is the output for n = 4, which contains several duplicates. Wiki Page Link: 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] 

Answer 1

In most modern programming languages, arrays are indexed to 0, and therefore for(int c=1;c<=n;c++){ not the right loop for iterating over elements. Pseudocode assumes a 1-indexed array.

Answer 2

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 that:

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

Answer 3

Try the following:

 //Heap 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 used the length of the input list instead of "n" for your swap

Answer 4

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

Answer 5

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

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

This starts with 1 (exists), then 2 (exists), then 3 (exists), then 4 (an array from the bound).

To fix, change the loop:

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

Answer 6

change list.length-1 to n-1 as your length is static

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[n-1]; list[n-1]=temp1; }else{ int temp2=list[0]; list[0]=list[n-1]; list[n-1]=temp2; } }