Algoritmo di Heap

Question

Tentativo di riprodurre l'algoritmo di Heap, per generare tutte le possibili permutazioni di un array di numeri interi, ma non posso risolverlo per altri interi di tre. algoritmo di Heap da 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]) 

Il mio codice:

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

Che cosa sto facendo di sbagliato e di incomprensione su di esso? Perché funziona solo con [1,2,3] (n = 3) come input e né con n = 2 né n = 4?

Funziona:

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) 

Grazie per le risposte, ma che non può essere il problema. Ho provato a cambiarlo prima di porre la domanda, ma pensare che partire da 1 è parte dell'algoritmo se comprendo correttamente la pagina Wiki come è esplicitamente indicato (anche se non si parla di alcun linguaggio/schema di ciclo particolare). Di seguito è riportato un output per n = 4 che contiene diversi duplicati. Link alla Wiki-pagina: 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

Nella maggior parte dei linguaggi di programmazione contemporanei le matrici sono 0 indicizzati e quindi for(int c=1;c<=n;c++){ non è un corretto ciclo per scorrere gli elementi. Lo pseudo codice presuppone un array con 1 indice.

Answer 2

Sei sicuro che c è limitato in alto dalla lunghezza dell'elenco?

Answer 3

Una serie di 4 ha gli indici 0, 1, 2 e 3. Java (e molte altre lingue) inizia a contare da 0. on line quattro si ha la seguente ciclo:

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

Questa dalle ore 1 (esiste), quindi 2 (esiste), quindi 3 (esiste), quindi 4 (matrice fuori limite).

Per fissare, modificare il loop:

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

Answer 4

Modifica questo:

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

A tal:

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 5

Prova questo:

//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); 

} 

Si stava utilizzando la lunghezza della lista di input invece di "n" per lo swap

Answer 6

cambiamento List.length-1 per n-1 come la lunghezza è statico

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