6

整数の配列のすべての可能な順列を生成するために、ヒープのアルゴリズムを再現しようとしていますが、3 以外の整数については解決できません。ウィキペディアのヒープのアルゴリズム:

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-schemeは言及されていませんが）、1から始めることはアルゴリズムの一部だと思います。以下は、いくつかの重複を含む 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

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 に答える
1

現代のほとんどのプログラミング言語では、配列のインデックスは 0 でfor(int c=1;c<=n;c++){あるため、要素を反復する正しいサイクルではありません。擬似コードは、1 インデックスの配列を想定しています。

于 2014-07-22T13:50:10.947 に答える
0

cリストの長さによって上に制限されていますか?

于 2014-07-22T13:50:15.887 に答える
0

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-22T13:51:03.170 に答える