Adding element to an ArrayList received as argument in recursive method?

Question

I have a method which performs permutation of an ArrayList elements, I give an ArrayList as parameter where to store the permutations. However, it's always adding the same item.

I think the issue about this is the ArrayList reference.

public class TSP {

    static ArrayList permute(ArrayList<Integer> arr, int k, ArrayList<ArrayList<Integer>> resultados) {
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            permute(arr, k+1, resultados);
            java.util.Collections.swap(arr, k, i);
        }

        if (k == arr.size() -1){

            System.out.println("Permute method: "+arr.toString());
            resultados.add(arr);
        }
        return resultados;
    }

    public static void main (String[] args) {

            ArrayList<Integer> ciudades = new ArrayList<>();
            ciudades.add(1);
            ciudades.add(2);
            ciudades.add(3);
            ArrayList<ArrayList<Integer>> resultados = new ArrayList();
            resultados = permute(ciudades, 0, resultados);

            for (ArrayList<Integer> resultado : resultados) {
                System.out.println(resultado.toString());
            }
    }
}

The output from execution is:

Permute method: [1, 2, 3]
Permute method: [1, 3, 2]
Permute method: [2, 1, 3]
Permute method: [2, 3, 1]
Permute method: [3, 2, 1]
Permute method: [3, 1, 2]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]

So everything's working OK inside the algorithm but only the first permutation is added. Why?

Lola · Accepted Answer · 2013-11-19 01:45:07Z

1

You are correct that it's the ArrayList reference. It's always pointed to the same object in memory, so the permute is always effecting ALL of the arrays in resultado. (Since they are all the same reference).

Changing the add line to:

resultados.add((ArrayList<Integer>)arr.clone());

will instead add a copy of the permuted array to resultados, and get you the output you're expecting.

answered Nov 19, 2013 at 1:45

Lola

1,9081 gold badge13 silver badges11 bronze badges

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

Collectives™ on Stack Overflow

Adding element to an ArrayList received as argument in recursive method?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related