6

试图重现堆的算法，以生成整数数组的所有可能排列，但我无法解决除三个以外的其他整数。来自维基百科的堆算法：

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 页面，我认为从 1 开始是算法的一部分，因为它明确说明（即使没有提到特定的语言/for-loop-scheme）。下面是 n=4 的输出，其中包含多个重复项。链接到 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]
4

5 回答 5

3

尝试这个：

//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-16T18:45:06.797 回答
1

在大多数当代编程语言中，数组是 0 索引的，因此for(int c=1;c<=n;c++){不是迭代元素的正确循环。伪代码假定 1-indexed 数组。

于 2014-07-22T13:50:10.947 回答
1

改变这个：

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-22T13:52:25.340 回答
0

你确定c上面是列表的长度吗？

于 2014-07-22T13:50:15.887 回答
0

4 的数组具有索引 0、1、2 和 3。Java（和许多其他语言）从 0 开始计数。在第四行，您有以下循环：

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

这从 1（存在）开始，然后是 2（存在），然后是 3（存在），然后是 4（数组超出范围）。

要修复，请更改循环：

for(int c = 0; c < n; c++){
于 2014-07-22T13:51:03.170 回答