CODEWITHSUNDEEP
javaarrayspermutation
guitarmansam87
guitarmansam87

Reputation: 13

After making permutations, how do I add them to an array? [Java]

I'm trying to, given some ArrayList of Integers, create all the permutations of that list. I want to store each permutation (an ArrayList itself) in a bigger ArrayList of ArrayLists. I can find the permutations and print each to the console without an issue. I haven't found a way to successfully add them to a list. My current attempt is shown below.

//myList is a field that I need to use elsewhere
//a is the ArrayList of Integers
//initially, n is a.size()
private static void perm2(ArrayList<ArrayList<Integer>> myList,
    ArrayList<Integer> a, int n)
{
    for (int i = 0; i < n; i++)
    {
        swap(a, i, n-1);
        perm2(where, a, n-1);
        swap(a, i, n-1);
    }
    if (n == 1)
    {
        System.out.println(a.toString());
        myList.add(a);
        return;
    }
}

Here is the output given [0, 1, 2]:

[1, 2, 0]
[2, 1, 0]
[2, 0, 1]
[0, 2, 1]
[1, 0, 2]
[0, 1, 2]
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

The print code is sending the right thing to the console, so why isn't it adding the right thing immediately after? If this isn't a good way to go about it, which direction should I look to? Ultimately, these are indices to retrieve data from a list in every order.

Thanks in advance.

I should note that the input list can be of arbitrary length, within reasonable computing capabilities.

EDIT: oversight on my part. Here's the swap code:

private static void swap(ArrayList<Integer> list, int a, int b)
{
    T temp = list.get(a);
    list.set(a, list.get(b));
    list.set(b, temp);
}

Upvotes: 1

Views: 308

Answers (3)

Oleg Gryb
Oleg Gryb

Reputation: 5259

Each time when you call 'add' method on myArray, elements of 'a' are not copied. myArray will hold a refernece to 'a' only. Since the reference is always the same, the latest state of 'a' element will be printed.

Try to print the content of myArray right after myArray.add(a) to see what I mean.

You do need to create a new instance of ArrayList to avoid this problem

Upvotes: 0

David Conrad
David Conrad

Reputation: 16419

You haven't shown us swap, but I assume it is modifying the list in place. The list of lists then contains multiple references to the same underlying list, which is in the final permuted state. Basically, you've put a mutable object into a list and then changed it, while expecting it to be in the state it was in when you first added it to the list.

One way to fix this is to make a defensive copy of the list at the time you add it:

myArray.add(new ArrayList<Integer>(a));

(Also, you call your variable myArray and say, "add them to an array", but myArray is a List and you are adding things to a list. I was a bit confused when I first read your question. You shouldn't refer to a list as an array.)

Upvotes: 2

JB Nizet
JB Nizet

Reputation: 692231

You always store the same list in the list of lists. Then you swap its elements and store it again. So you end up with N references to the same list. You need to make a copy of the list before storing it in the list of lists:

myArray.add(new ArrayList<>(a));

Upvotes: 5

Related Questions