Why does Collections.shuffle() fail for my array?

Question

Why does my code not work?

package generatingInitialPopulation;

import java.util.Arrays;
import java.util.Collections;

public class TestShuffle {
    public static void main(String[] args) {
        int[] arr = new int[10];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        Collections.shuffle(Arrays.asList(arr));

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

The result is: 0 1 2 3 4 5 6 7 8 9.

I was expecting a randomly shuffled sequence.

Olgaolguin

Answer 1

Arrays.asList() can't be applied to arrays of primitive type as you expect. When applied to int[], Arrays.asList() produces a list of int[]s instead of list of Integers. Therefore you shuffle a newly created list of int[].

This is a subtle behaviour of variadic arguments and generics in Java. Arrays.asList() is declared as

public static <T> List<T> asList(T... a)

So, it can take several arguments of some type T and produce a list containing these arguments, or it can take one argument of type T[] and return a list backed by this array (that's how variadic arguments work).

However, the latter option works only when T is a reference type (i.e. not a primitive type such as int), because only reference types may be used as type parameters in generics (and T is a type parameter).

So, if you pass int[], you get T = int[], and you code doesn't work as expected. But if you pass array of reference type (for example, Integer[]), you get T = Integer and everything works:

Integer[] arr = new Integer[10]; 

for (int i = 0; i < arr.length; i++) { 
    arr[i] = i; 
} 

Collections.shuffle(Arrays.asList(arr)); 

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

Analyst

WOW!!! But everyone said that the changes applied for the list, not with the array arr. Why does this work? – Olgaolguin

Because Arrays.asList() creates a new list that is backed by the array. It does not copy the array as others have stated. Every change to the list returned by Arrays.asList() also changes the array backing it. – Brain

Understood now. But why that doesn;t work with the primitive types? – Olgaolguin

@Dmitry: Because Java generics don't work with primitive types. See, Arrays.asList() returns List<T>, but you can't declare List<int> in Java. – Analyst

T cannot be a primitive type, so in a sense this shouldn't compile for a primitive type. However, because of the varargs, it is valid to call asList with a single object, and it will treat it as an array of size 1. As such, it will compile and work in a confusing way. – Coconut

@Analyst I was debugging this code, and found that code is not going inside for loop mentioned in below code.public static void shuffle(List<?> list, Random rnd) { int size = list.size(); if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { for (int i=size; i>1; i--) swap(list, i-1, rnd.nextInt(i)); } – Stuckey

To add to what @Brain said, to create a a list from an array which is not backed by that array you should use List l = new ArrayList(Arrays.asList(arr)); to create a LinkedList simply change ArrayList to LinkedList – Homochromous

Answer 2

Try adding this line of code to your test:

List l=Arrays.asList(arr);
System.out.println(l);

You will see you are printing out a single element List.

Using Arrays.asList on a primitive array cause asList to treat the int[] as a single object rather than an array. It returns a List<int[]> instead of a List<Integer>. So, you are basically shuffling a single element List and so nothing really gets shuffled.

Notice that some of the answers already given are wrong because asList returns a List backed by the original array, nothing gets copied - all changes are reflected in the orginal array.

Tumbler

But why does this work in a such way with the primitive type int(treats int[] as a single object)? – Olgaolguin

@Dmitry: Arrays are also Objects in Java and I guess the arguments of asList(T...) is interpreted as simple a single Object, since asList does not expect primitives. – Tumbler

Answer 3

That doesn't work because the call to shuffle is operating on the List returned by Arrays.asList, not on the underlying array. Thus, when you iterate over the array to print out the values, nothing has changed. What you want to do is save a reference to the List returned by Arrays.asList, and then print out the values of that List (rather than the values of the array) after you shuffle it.

Eberhardt

The API says - "Returns a fixed-size list backed by the specified array. (Changes to the returned list "write through" to the array.)" - download.oracle.com/javase/6/docs/api/java/util/… – Lancastrian

Thank you for the immediate answer! – Olgaolguin

Wrong, any changes made to the list created by Arrays.asList() is made to the array itself - the list uses that array to store the elements. The problem is that asList can not create a list of primitives, so it creates a list with one element: the array itself. It would work for an array with non-primitives (e.g. Integer). – Lai

Answer 4

Store the list resturned by Arrays.asList and shuffle that...

List myShuffledList = Arrays.asList(arr);
Collections.shuffle(myShuffledList);

Primrose

it's much better to use generic types instead of raw types – Seale