ArrayList of int[] in a recursive method

Question

I have a project to do for school in which i have to use a recursive method that will calculate all the switching possibilities between some numbers. I.E : [1,2] => 1,2 and 2,1.

So i've used this method and it seemed to be working properly when i just print the solutions on the console, but when i want to stock the tabs in an ArrayList (i need to use them later) it will always add the same order. In my exemple it would have added 1,2 and 1,2 instead of 1,2 and 2,1.

Here's my code :

public  static void permute(int start, int[] input, ArrayList <int[]> al) { 
    //This method is recursive, it will open multiple instances of the input tab by calling itself and modify them, then stock tab in ArrayList when the operations are done for this tab.
    //ArrayList must be empty.

    //Printing tab if iterations for that specific tab are done
    if (start == input.length) {
        al.add(input);
        ////////////////////////////////
        // For printing tabs in console.
        // for(int x: input){
        // System.out.print(x);
        // }
        // System.out.println("");
        ////////////////////////////////
    //End the specific tab loop when it's printed 

    return;
    }
    for (int i = start; i < input.length; i++) {
        // Changing numbers
        int temp = input[i];
        input[i] = input[start];
        input[start] = temp;

        //////////////////////////////////////////////////
        // Tests to see algorithm steps
        //
        // System.out.print("temp : " + temp + " ... ");
        // System.out.print("i : "+i + " ... ");
        // System.out.print("start : " + start);
        // System.out.println("");
        // System.out.print("---");
        // for(int x: input){
        //  System.out.print(x);
        // }
        // System.out.println("");
        //////////////////////////////////////////////////

        //Changing numbers
        permute(start + 1, input, al);

       // Changing numbers
        int temp2 = input[i];
        input[i] = input[start];
        input[start] = temp2;

}

}

I use start = 0, input = {1,2,3} and the ArrayList is empty before the method starts.

Hope you can help, thanks !

Edd · Accepted Answer · 2017-03-29 11:49:51Z

1

The problem is that you are adding a reference to an array into your ArrayList, reference that you then keep changing in your algorithm.

By the end of it, you will have perm(N) copies of the same array.

All you have to do is to add a deep-copy of the array into the ArrayList, like this:

al.add(Arrays.copyOf(input, input.length));

instead of

al.add(input);

Printing the resulting ArrayList will then produce the following output:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

answered Mar 29, 2017 at 11:49

Edd

1,38011 silver badges14 bronze badges

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

2 Comments

Lucien Ledune Over a year ago

Thanks man it worked ! But can I ask you the difference between my line and the deep-copy ? I mean when should I use the deep-copy over the input reference?

Edd Over a year ago

You want to use deep-copy anytime you want to get a real new copy of the object, rather than just a copy of the current reference to the Object. the latter, will not safeguard you against other code modifying the underlying object through the reference they hold, exactly what was tripping you here. To understand why this is necessary, google for "is java pass by reference or value?"

Collectives™ on Stack Overflow

ArrayList of int[] in a recursive method

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related