2

配列 A の要素のすべての順列を見つけるためのヒープ アルゴリズムを実装しました。 

//A = {1, 2, 3, 4}; B = perms(A) ; num_row(B) = (4!+1) and B[0][0] = 4!;
//This is B.R. Heap's algorithm
public static void perms(int [] A, int [][]B, int n)
{
   if (n == 1)
   {
       int k = B[0][0];
       for (int i = 0; i < A.length; i++)
       {
           B[k + 1][i] = A[i];
       }
       B[0][0]++;
   }
   else
   {
       for (int i = 0; i < n - 1 ;i++)
       {
           perms(A, B, n-1);
           if (n % 2 == 0)
           {
               swap(A, i, n - 1);
           }
           else
           {
               swap(A, 0, n - 1);
           }
       }
       perms(A, B, n - 1); 
   }
}
public static void swap(int[] A, int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

私はJavaが初めてです。問題は、関数 perms(A) の出力 (戻り値) として B を使用したいのですが、この実装では int[n! を初期化する必要があります。+ 1][A.length] 関数を呼び出す前の B 配列。どうすればいいですか？
再帰関数が以前の呼び出しから変数を記憶するのを助けるために、プライベート変数やJavaのようなものはありますか?

ありがとう

4

1 に答える 1

1

次のように、再帰への「入力」メソッドを作成できます。

public static int[][] perms(int[] a){
    int[][] perms = new int[factorial(a.length)+1][a.length];
    perms(a,perms,a.length);
    return perms;
}

メソッドfactorialはよく知られているメソッドであり、たとえばGoogleで見つけることができます パラメータが
必要かどうか疑問に思うn

編集

必要ありません（上記修正済み）

編集

私のテストでは、k変数は増加しているだけなので、次のように静的変数を使用します。

private static int counter = 0;
// your code here, following is a part of your perms method
if (n == 1)
{
    for (int i = 0; i < A.length; i++)
    {
        B[counter][i] = A[i];
    }
    counter++;
}
//and my code corrected too:
public static int[][] perms(int[] a){
    int[][] perms = new int[factorial(a.length)][a.length]; //+1 is not necessary
    counter=0; //necessary to call it again
    perms(a,perms,a.length);
    return perms;
}
于 2015-07-07T08:24:35.793 に答える