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

vidit · Accepted Answer · 2013-04-11 02:48:45Z

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

edited Apr 11, 2013 at 2:48

answered Apr 11, 2013 at 1:52

vidit

6,5013 gold badges36 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Chris Cirefice Over a year ago

thank you for the suggestion. I understand now why the copying is necessary, and I've made changes to reflect that in my code. It is 50% working now. If you run the method, you will notice that the output is the following: 1, 2, 3 , 1, 2, 3 , 2, 1, 3 , 2, 1, 3 , 3, 2, 1 , 3, 2, 1. This is not entirely strange and I'm sure it has to do with one of the swap statements, but I can't figure out why it's no swapping the set in each pair of duplicates. I've been staring at this for a while though, perhaps it's just a glaring error that I'm glancing over...

vidit Over a year ago

@ChrisCirefice - I have added a live example.. hope that helps.

Chris Cirefice Over a year ago

Okay, I fixed it! It was the swap operation, the second one to be specific. I made a copy of the "previous permutation" of the int[], and was swapping back and forth the values of the copied array, but I should have been swapping back the values of the original (while swapping forward the values of the copied array)... make sense? In any case, I'll update the code after this comment to reflect the changes. Hopefully somebody else stumbles across this problem in the future and finds my code and your copy idea helpful! Oh, and I see what you meant by null now... that also works :P

Zim-Zam O'Pootertoot · Accepted Answer · 2013-04-11 01:53:01Z

0

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

answered Apr 11, 2013 at 1:53

Zim-Zam O'Pootertoot

18.2k4 gold badges45 silver badges71 bronze badges

Comments

Code-Apprentice · Accepted Answer · 2013-04-11 01:54:47Z

0

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.

answered Apr 11, 2013 at 1:54

Code-Apprentice

84k26 gold badges162 silver badges289 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related