堆的算法

试图重现堆的算法，用于生成一个整数数组的所有可能的排列，但我不能解决它比其他三个整数。堆的维基百科算法：堆的算法

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

我的代码：

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

我在做什么错误和误解呢？为什么它只能使用[1,2,3]（n = 3）作为输入，既不能使用n = 2也不能使用n = 4？

上运行：

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)

感谢您的答复，但不能成为问题。在我问这个问题之前，我尝试过改变它，但是如果我正确理解Wiki页面（即使没有提及特定的语言/ for-loop方案），从1开始是算法的一部分。以下是n = 4的输出，其中包含多个重复项。链接到维基页：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]

来源

2014-07-22 user2069136

可能[堆的算法排列生成器]（http://stackoverflow.com/questions/29042819/heaps-algorithm-permutation-generator） – rici

更好的迟到比从未，我想。在链接问题中探讨了维基百科文章中的错误和修复（在Python中，加上伪代码）。 – rici

在最现代的编程语言中数组索引0，因此for(int c=1;c<=n;c++){不是一个正确的循环遍历元素。伪代码采用1索引数组。

来源

2014-07-22 13:50:10

感谢您的回复，但不要认为这是问题，请参阅我上面的修改。 – user2069136

你确定c是由列表的长度以上？

来源

2014-07-22 13:50:15

的4所述的阵列具有索引0，1，2和3的Java（和其它语言）从0开始计数在4线则有以下循环：

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

这开始于1（存在），然后2（存在），然后3（存在），然后4（数组越界）。

要修复，改变循环：

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

来源

2014-07-22 13:51:03 Cheiron

更改此：

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

要这样：

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

来源

2014-07-22 13:52:25

感谢您的回复，但我不认为这是问题，而是算法的一部分。请参阅我上面的编辑。 – user2069136

试试这个：

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

}

您使用的输入列表，而不是 “N” 的长度为您的交换

来源

2015-01-16 18:45:06 brunoma

变化list.length-1，N-1作为你的长度是静态

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

来源

2015-01-30 22:17:53 Viajante80

回答

相关问题