logo标签列表

Heap's算法

javapermutationheaps-algorithm
6

我正在尝试复制Heap算法，用于生成整数数组的所有可能排列，但我无法解决除三以外的其他整数。

Heap算法来自维基百科：

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)

感谢回复，但这不可能是问题所在。在我提出问题之前，我已经尝试更改了那个部分，但是如果我正确理解维基页面，从1开始是算法的一部分，因为它被明确说明了（尽管没有特定的语言/for-loop-scheme）。以下是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]
可能是Heap算法排列生成器的重复问题。 - rici
1
我想说，迟做总比不做好。链接的问题中探讨了维基百科文章中的错误以及修复方法（使用Python和伪代码）。 - rici
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”。
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;
            }
        }
    }
}
谢谢回复，但我认为那不是问题，而是算法的一部分。请参见我上面的编辑。 - user2069136
1
在大多数现代编程语言中，数组是从0开始索引的，因此for(int c=1;c<=n;c++){不是正确的循环迭代元素的方法。伪代码假设数组从1开始索引。
谢谢您的回复，但我不认为那是问题所在。请看我上面的编辑。 - user2069136
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++){
0
你确定 c 的上限是列表的长度吗？
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接