Heap's Algorithm implementation in list of lists

Question

I'm using Heap's algorithm to create a list-of-lists containing each permutation of said list. Each permutation will be its own list. It works properly when I print it within the algorithm, but it doesn't work properly when I try to add it to my list-of-lists and they are all the same array (4, 1, 2, 3). I commented out the print that I tested to make sure it was working.

My current code:

public static ArrayList<int[]> lists = new ArrayList<>();

public static void main(String[] args) {
    int[] list = {1,2,3,4};
    heapsAlgorithm(4,list);
    for(int i = 1; i <= lists.size(); i++) {
        System.out.println("List " + i + ": " + Arrays.toString(lists.get(i-1)));
    }
}

public static void heapsAlgorithm(int n, int[] list) {
    if (n == 1) {
        lists.add(list);
        //System.out.println(Arrays.toString(list));
    }
    else {
        for(int i = 0; i < n; i++) {
            heapsAlgorithm(n - 1, list);
            if ( n % 2 == 0) {
                int swap = list[i];
                list[i] = list[n-1];
                list[n-1] = swap;
            }
            else {
                int swap = list[0];
                list[0] = list[n-1];
                list[n-1] = swap;
            }
        }
    }
}

Working:

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

Incorrect output:

List 1: [4, 1, 2, 3]
List 2: [4, 1, 2, 3]
List 3: [4, 1, 2, 3]
List 4: [4, 1, 2, 3]
List 5: [4, 1, 2, 3]
List 6: [4, 1, 2, 3]
List 7: [4, 1, 2, 3]
List 8: [4, 1, 2, 3]
List 9: [4, 1, 2, 3]
List 10: [4, 1, 2, 3]
List 11: [4, 1, 2, 3]
List 12: [4, 1, 2, 3]
List 13: [4, 1, 2, 3]
List 14: [4, 1, 2, 3]
List 15: [4, 1, 2, 3]
List 16: [4, 1, 2, 3]
List 17: [4, 1, 2, 3]
List 18: [4, 1, 2, 3]
List 19: [4, 1, 2, 3]
List 20: [4, 1, 2, 3]
List 21: [4, 1, 2, 3]
List 22: [4, 1, 2, 3]
List 23: [4, 1, 2, 3]
List 24: [4, 1, 2, 3]

I assume I am using my ArrayList wrong, but I'm not sure where. Any suggestions?

You need to add a copy of the array to the list: lists.add(Arrays.copyOf(list, list.length)). — Andy Turner
– Andy Turner, Commented Sep 15, 2017 at 18:42
Thanks! That worked. Any reasoning behind why adding a copy of the array works rather than just directly adding the array? — Display Name
– Display Name, Commented Sep 15, 2017 at 18:47
Because adding the array (or anything, generally) to the list doesn't copy the it: you are just storing a reference. As such, any updates to the array "outside" the list are also updates to the same array "inside" the list. — Andy Turner
– Andy Turner, Commented Sep 15, 2017 at 18:52
This is not a correct implementation of Heap's algorithm. You might have been misled by the geeksforgeeks site, which is just wrong, or by looking at the Wikipedia page at a moment when it has been defaced by someone who thinks they know better, normally because they've looked at another erroneous site. Heap's algorithm swaps exactly two elements at each iteration. The erroneous implementation does not conform to this restriction; see the seventh step where it transitions from 3,2,1,4 to 4,2,3,1, which is clearly not one swap since three elements have been moved. — rici
– rici, Commented Sep 15, 2017 at 22:02

B. Pleshakov · Accepted Answer · 2017-09-15 18:49:58Z

1

You are need to copy your int array.

You have an mutable instance of your array and list of arrays that you assume you to keep your permutations. Basically, what's happening:

You do permutation.
You add permutation to your ArrayList.
You do another permutation on THE SAME object.
You add object to ArrayList that ALREADY in this list.

At the end you have ArrayList with 20 times added the same int array.

answered Sep 15, 2017 at 18:49

B. Pleshakov

11610 bronze badges

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

Collectives™ on Stack Overflow

Heap's Algorithm implementation in list of lists

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related