Error generating permutations using Heap's Algorithm

Question

Objective of my code: Trying to create an ArrayList of Arrays containing all permutations of passed array 'p'.

Approach: Using Heap's algorithm, trying to generate all permutations, each permuatation bieng stored in and ArrayList using add() method.

Problem code is getting into: All elements in ArrayList gets updated to same value(that of latest permutation found).

CODE:

import java.io.IOException;
import java.util.ArrayList;

class Main
{
   static ArrayList<int[]> arrayList=new ArrayList<>();

    static void getCombo(int[] p, int size, int n){

        if(size==1){
            arrayList.add(p);
            System.out.println("added new permutation");
            for(int i=0;i<arrayList.size();++i){
                for(int j:arrayList.get(i)) {
                    System.out.print(j);}
                System.out.println("");
                }
        }

        for (int i=0; i<size; i++)
        {
            getCombo(p,size-1, n);
            // if size is odd, swap first and last
            if ((size&1)!=0) p[0]=p[0]^p[size-1]^(p[size-1]=p[0]) ;
                // If size is even, swap ith and last
            else p[i]=p[i]^p[size-1]^(p[size-1]=p[i]) ;
        }
    }


    public static void main(String args[]) throws IOException {
        int[] arr={1,2,3} ;
        getCombo(arr, arr.length,arr.length);
    }

}

O/P Of code:

added new permutation
123
added new permutation
213
213
added new permutation
312
312
312
added new permutation
132
132
132
132
added new permutation
231
231
231
231
231
added new permutation
321
321
321
321
321
321

Desired O/P: The list should contain distinct permutations being added in every iteration.(Here in this case 6 such permutations exist.)

IF I REMOVE ARRAYLIST, and JUST SIMPLY USE PRINT TO GET THE PERMUTATIONS, THE PERMUTATIONS ARE ALL CORRECTLY GENERATED BY THIS CODE...

import java.io.IOException;
import java.util.ArrayList;

class Main
{
   static ArrayList<int[]> arrayList=new ArrayList<>();

    static void getCombo(int[] p, int size, int n){

        if(size==1){
            for(int i:p) System.out.print(i);
            System.out.println();
        }

        for (int i=0; i<size; i++)
        {
            getCombo(p,size-1, n);
            // if size is odd, swap first and last
            if ((size&1)!=0) p[0]=p[0]^p[size-1]^(p[size-1]=p[0]) ;
                // If size is even, swap ith and last
            else p[i]=p[i]^p[size-1]^(p[size-1]=p[i]) ;
        }
    }


    public static void main(String args[]) throws IOException {
        int[] arr={1,2,3} ;
        getCombo(arr, arr.length,arr.length);
    }

    }

O/P:
123
213
312
132
231
321

Question/Query:

Kindly tell why this is happening, as if I opt to print the array 'p' directly in each if(size==1) condition, then o/p is correct, only ArrayList implementation is creating issue...
What's the fix for this? (most efficient fix preferably).

It looks like you only have one array. You're manipulating the same array. So when you add it, it looks one way, but then you change it.. — Scratte, Feb 21 '20 at 19:29
Actually - I thought `static` was the issue but upon further inspection it seems to be an error with your logic. Have you tried working with some Heap's Algorithm pseudocode? — sleepToken, Feb 21 '20 at 19:31
Kindly look at the edit in my question, just added one more code in which o/p is generated in console rather than storing in ArrayList, it's coming out to be correct...hope this could give a better insight to readers to help me... — Kartik Gautam, Feb 21 '20 at 19:39

azurefrog · Accepted Answer · 2020-02-21T19:57:46.960

As @Scratte pointed out, you're only ever adding one array (p) to your list. You add multiple references to it, but it's always the same array under the covers, so if you modify the array you'll always see the same data each time you print it.

What you want to do instead is add the data contained in p to your arraylist instead. You can trivially do this adding p.clone() instead of p (See Clone method for Java arrays for more detail on the mechanics of this).

Then when you change p further along in your program, you won't also modify the stored data.

If I change your code from

static void getCombo(int[] p, int size, int n) {
    if (size == 1) {
        arrayList.add(p);
        ...

to

static void getCombo(int[] p, int size, int n) {
    if (size == 1) {
        arrayList.add(p.clone());
        ...

I get this output:

added new permutation
123
added new permutation
123
213
added new permutation
123
213
312
added new permutation
123
213
312
132
added new permutation
123
213
312
132
231
added new permutation
123
213
312
132
231
321

I almost hit "Post Your Answer", but you beat me to it. I used System.arraycopy(..) as the only difference to your answer. — Scratte, Feb 21 '20 at 19:50
You could also use `Arrays.copyOf(p, p.length)`. There sure are lots of ways to copy arrays in Java... ;-) — azurefrog, Feb 21 '20 at 19:54

Error generating permutations using Heap's Algorithm

1 Answers1