0

尝试在递归方法中添加int[]一段时间时遇到了一些麻烦。List<int[]>我正在获取所有int[]大小的排列N以用于不同的功能。我想将这些排列中的每一个都添加到前面提到的列表中。但是，似乎不能为所有排列添加 int[] (shortestPath)，老实说，我没有足够的递归经验来知道为什么每个数组的打印输出有效，但是添加到 List 只是添加第一个 arr （作为参数传递的那个） 6 次。

我的代码如下：

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。您应该创建一个新数组，交换然后将其添加到列表中。

更新：更详细一点..

您在 main 中创建一个新数组arr，然后将引用（按值）传递给permute函数。在 else 部分，您交换数组引用中的两个整数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

这里有几个排列代码的例子，希望能帮助你

于 2013-04-11T01:53:01.050 回答
0

请记住，数组是一个对象。这意味着参数arr是对对象的引用。每个递归调用都将引用同一个数组，因此任何更改都将反映在您使用该数组引用的任何地方。这也意味着每次调用时，shortestPaths.add(arr);您都会一遍又一遍地添加对完全相同的数组的引用。因此，您的列表将包含对同一数组对象的许多引用。

话虽如此，为了做你想做的事，你需要在每次想要进行更改时复制数组并将其添加到你的List.

于 2013-04-11T01:54:47.253 回答