Java Recursion with List<int[]>.add() Repeat Values

Question

I'm having a bit of trouble with trying to add an int[] to a List<int[]> while in a recursive method. I'm getting all permutations of an int[] of size N to use with a different function. I want to add each one of these permutations to the previously-mentioned list. However, it doesn't seem that the int[] (shortestPath) can be added for all permutations, and honestly I don't have enough experience with recursion to know why the printouts of each array work, but adding to the List simply adds the first arr (the one passed as the parameter) 6 times.

My code is as follows:

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");
}

P.S. - The printouts are just there for a quick view of the state of the data structures. They will of course be removed when the implementation is fully functional :) Also, this code is nested in a class that has many more functions related to matrix processing. This function in particular is a helper function for a shortest path algorithm.

Thanks in advance to those who know recursion better than I and who are willing to help!

Chris

Answer 1

You are modifying and adding the reference to the same array arr everytime you call add. You should create a new array, swap and then add it to the list.

UPDATE: A little more detail..

You create a new array arr in main, then pass the reference(by value) to the permute function. In the else part, you swap two integers in the array reference arr(you are not creating a new array, just modifying the same one) and add it to the list. Next iteration, the same thing happens with the same array reference arr, adding the same array again to the list.

Here's what you should do instead..

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.
}

There might be a better way, but I'm not an expert either.

Update 2: Live example.. http://ideone.com/vHcz7b

_{P.S: Can someone format this for me?}

Answer 2

Remember that an array is an object. This means that the parameter arr is a reference to the object. Each recursive call will have a reference to the same array so any changes will be reflected anywhere you use a reference to that array. This also means that each time you call shortestPaths.add(arr); you are adding a reference to the exact same array over and over and over again. So your list will contain many references to the same array object.

With that said, in order to do what you want, you need to make a copy of the array each time you want to make a change and add it to your List.

Answer 3

Here are several examples of permutation code that hopefully will help you out