Permutation of int[] array-adding to list

Question

I have an algorithm to count each permutation of an int array. In this case - when I want to print these permutations - everything worked fine. But if I want to save the arrays to the arraylist, it saved the correct number of them, but it saved only the one same option. I know that the problem will be trivial, but I can't solve it. Thanks for your help.

I add to the method printArray, that it saved the printed Array to Arraylist afterwards. Output of printArray is correct, but output of printList is like this:

1 2 3 4 5 6

(and this input is printed n!, which is correct but its only one permutation)

Here is my code:

public class Permute {

ArrayList<int[]> list;

public Permute() {
    list=new ArrayList<>();
}

void printArray(int[] a) {
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i] + " ");
    }
    System.out.println("");

    list.add(a);
}

void printList(){
    for(int[] arr:list){
        for(int item:arr){
            System.out.print(item+" ");
        }
        System.out.println("");
    }
}



void permute(int[] a, int k) {
    if (k == a.length)
        printArray(a);
    else {
        for (int i = k; i < a.length; i++) {
            int temp = a[k];
            a[k] = a[i];
            a[i] = temp;
            permute(a, k + 1);
            temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }
}
public static void main(String[] args) {
    Permute p = new Permute();
    int a[] = {1, 2, 3, 4, 5, 6};
    p.permute(a, 0);
    p.printList();
}

}

You are always adding the same array (a) to the list. Later changes to that array are then reflected in all references. Add a copy of a to the list each time: list.add(Arrays.copyOf(a, a.length)) — user2390182
– user2390182, Commented Feb 27, 2016 at 20:55
@schwobaseggl so when i change the array a it changes also the array in arraylist ? How can I add only copy? — preneond
– preneond, Commented Feb 27, 2016 at 20:59
See my updated comment: basically, you have to create a new array for each permutation (which the Arrays.copyOf method does). Generally I would do the copy first, and then do the changes in order to leave your initial array unharmed. — user2390182
– user2390182, Commented Feb 27, 2016 at 21:02

RealSkeptic · Accepted Answer · 2016-02-27 20:59:29Z

1

You are using the same array over and over again. You rearrange the items inside it.

It's fine when you print it. But when you come to save it in a list, what gets saved is the array reference, not the array contents.

So you enter a reference to the same object n! times into the the list. At the end of the operation, all those references still refer to the same object - and printing the list will print that same array again and again, with the most recent contents it has.

If you want to save the different contents each time, you'll need to make a copy of the array, and save that copy.

So, for example, you can use

list.add( Arrays.copyOf(a, a.length) );

answered Feb 27, 2016 at 20:59

RealSkeptic

34.8k7 gold badges56 silver badges83 bronze badges

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

1 Comment

preneond Over a year ago

Thanks, i use a.clone() and it worked as well. So silly mistake,haha :D

Collectives™ on Stack Overflow

Permutation of int[] array-adding to list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related