0

再帰的なメソッドで aint[]に aを追加しようとすると、少し問題が発生します。別の関数で使用するサイズのList<int[]>順列をすべて取得しています。これらの順列のそれぞれを前述のリストに追加したいと思います。ただし、すべての順列に int[] (shortestPath) を追加できるとは思えません。正直なところ、各配列の出力が機能する理由を知るには、再帰の経験が十分ではありませんが、リストに追加すると単純に追加されます最初の arr (パラメーターとして渡されたもの) 6 回。int[]N

私のコードは次のとおりです。

public int counter = 0;
public List<int[]> shortestPaths = new ArrayList<int[]>();

public void permute(int[] arr, int startIndex) {

    int size = arr.length;

    if (arr.length == (startIndex + 1)) {
        System.out.print("Permutation " + counter + " is: ");
        for (int i = 0; i < size; i++) {
            if (i == (size - 1)) System.out.print(arr[i] + "\n\n");
            else System.out.print(arr[i] + ", ");
        }
        shortestPaths.add(arr);
        counter++;
    } else {
        for (int i = startIndex; i < size; i++) {
            int[] copy = arr.clone();

            int tmp = copy[i];
            copy[i] = copy[startIndex];
            copy[startIndex] = tmp;

            permute(copy, startIndex + 1);

            //tmp = arr[i];
            //arr[i] = arr[startIndex];
            //arr[startIndex] = tmp;
            copy = null;
        }
    }
}

public static void main(String[] args) {

    int[] arr = { 1, 2, 3 };
    permute(arr, 0);

    System.out.print("\n\n\n\n");
    for (int[] a : s.shortestPaths) {
        System.out.println(a[0] + ", " + a[1] + ", " + a[2] + "\n\n");
}

PS - 印刷物は、データ構造の状態をすばやく確認するためのものです。もちろん、実装が完全に機能するようになると削除されます:) また、このコードは、マトリックス処理に関連するさらに多くの関数を持つクラスにネストされています。特にこの関数は、最短パス アルゴリズムのヘルパー関数です。

私よりも再帰をよく知っていて、喜んで助けてくれる人たちに、前もって感謝します!

Chris

4

3 に答える 3

1

arrを呼び出すたびに、同じ配列への参照を変更および追加していますadd。新しい配列を作成し、スワップしてからリストに追加する必要があります。

更新:もう少し詳細..

メインで新しい配列arrを作成し、参照を (値で)permute関数に渡します。else 部分では、配列参照の 2 つの整数を交換しarr(新しい配列を作成するのではなく、同じ配列を変更するだけです)、addそれをリストに入れます。次の反復では、同じ配列参照arrで同じことが起こり、同じ配列が再びリストに追加されます。

代わりにすべきことは次のとおりです..

else {
  int[] tempArr = new int[arr.length]; 
  System.arraycopy(arr, 0, tempArr, 0, arr.length);

  // swap in the tempArr
  // add tempArr to the list
  // after that if you want you can set tempArr to null, to avoid loitering.
}

もっと良い方法があるかもしれませんが、私も専門家ではありません。

更新 2: 実例.. http://ideone.com/vHcz7b

PS: 誰かが私のためにこれをフォーマットできますか?

于 2013-04-11T01:52:41.277 に答える
0

配列はオブジェクトであることを思い出してください。これは、パラメータarrがオブジェクトへの参照であることを意味します。各再帰呼び出しには同じ配列への参照があるため、その配列への参照を使用するすべての場所に変更が反映されます。これは、呼び出すたびshortestPaths.add(arr);に、まったく同じ配列への参照を何度も何度も追加していることも意味します。したがって、リストには同じ配列オブジェクトへの参照が多数含まれます。

そうは言っても、必要なことを行うには、変更を加えるたびに配列のコピーを作成し、それを に追加する必要がありますList。

于 2013-04-11T01:54:47.253 に答える
0

うまくいけばあなたを助ける順列コードのいくつかの例を次に示します

于 2013-04-11T01:53:01.050 に答える