Java random shuffle list with two elements using Collections.shuffle

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class ShuffleList {
  public static void main(String[] args) {
    String [] file = {"1","2"};
    long seed = 3;
    ArrayList<String> fileList = new ArrayList<String>(Arrays.asList(file));
    for (int i=0; i<200; i++) {
      Collections.shuffle(fileList, new Random(seed));
      seed = seed +1;
      System.out.println(seed + "," + fileList);
    }
  }
}

The output is 200 lines of [1,2], not random shuffle at all. In fact this is true for all seed < 4000. Why is that? I tried with a list of 3 elements and seeds from 1 to 100 makes the list seemingly random. But what's wrong with a list of 2 elements?

Jon Skeet
people
quotationmark

The problem isn't with shuffle - it's with Random with small seeds. Here's a program demonstrating that:

import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int total = 0;
        for (int seed = 0; seed < 4000; seed++) {
            Random rng = new Random(seed);
            total += rng.nextInt(2);
        }
        System.out.println(total);
    }
}

You'd expect an output of about 2000 - about half calls to nextInt should return 0, and about half should return 1. Instead, it's 4000 - every call returns 1.

Using seeds [10000, 13999) you get 240 - so vastly more of the calls return 0 than 1.

Using seeds [100000, 103999) you get 3226 - getting a bit better...

Using seeds [1000000, 1003999) you get 2105 - much better.

I don't know nearly enough about the maths of RNGs to say why this happens, but it does look like java.util.Random is kinda broken for small seeds.

people

See more on this question at Stackoverflow