Algorytm sterty

Question

Próba odtworzenia algorytmu Heap, w celu wygenerowania wszystkich możliwych permutacji tablicy liczb całkowitych, ale nie mogę jej rozwiązać dla innych liczb całkowitych niż trzy. algorytm z Wikipedii sterty:

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]) 

Mój kod:

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

Co robię źle i nieporozumień na ten temat? Dlaczego działa tylko z [1,2,3] (n = 3) jako danych wejściowych, a nie z n = 2 ani n = 4?

zjazdowe:

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) 

Dzięki za odpowiedzi, ale to nie może być problem. Próbowałem to zmienić, zanim zadałem pytanie, ale myślę, że począwszy od 1 jest częścią algorytmu, jeśli dobrze rozumiem stronę Wiki poprawnie, ponieważ jest to wyraźnie określone (nawet jeśli nie wspomniano o żadnym konkretnym języku/schemacie pętli for). Poniżej znajduje się wynik dla n = 4, który zawiera kilka duplikatów. Link do strony wiki: 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

W większości języków programowania współczesnych tablice są indeksowane 0, a więc for(int c=1;c<=n;c++){ nie jest prawidłowy cykl iteracyjne nad elementami. Pseudo kod zakłada tablicę 1-indeksową.

Answer 2

Czy jesteś pewien, że c jest ograniczony powyższą długością listy?

Answer 3

Tablica 4 ma indeksy 0, 1, 2 i 3. Java (i wielu innych językach) Rozpocznij liczenie na 0. W linii czterech masz następującą pętlę:

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

Zaczyna się 1 (istnieje), następnie 2 (istnieje), następnie 3 (istnieje), następnie 4 (macierz poza oprawą).

Aby naprawić, zmienić pętlę:

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

Answer 4

to zmienić:

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

do tego:

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

Spróbuj tego:

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

} 

uzywasz długość listy wejściowej zamiast "n" do zamiany

Answer 6

zmiana list.length-1 do n-1 jako swojej długości jest statyczna

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