Java.util.Collection.Shuffle not producing random results when using a seeded Random

Question

Given the following code:

        List<Integer> consensusGroupOrder = new ArrayList<>();

        for (int i = 0; i < numberOfItems; i++) {
            consensusGroupOrder.add(i + 1);
        }

        Collections.shuffle(consensusGroupOrder, new Random(seed));

        int count = 1;

        Map<Integer, Integer> returnValue = new HashMap<>();

        for(Integer group: consensusGroupOrder) {
            returnValue.put(count++, group);
        }

When I set numberOfItems to 4 and starting with a seed of 1, when dumping returnValue as Json I get:

{
  "1": 4,
  "2": 1,
  "3": 2,
  "4": 3
}

Incrementing seed, the fourth item in the list is always 3. Seed = 5:

{
  "1": 4,
  "2": 1,
  "3": 2,
  "4": 3
}

Seed = 10:

{
  "1": 2,
  "2": 4,
  "3": 1,
  "4": 3
}

Seed = 255:

{
  "1": 1,
  "2": 2,
  "3": 4,
  "4": 3
}

I am seeding Random as I need the result to be deterministic based on seed, but why is the 4th item always 3? Only when seed = 256 does the fourth item change.

I found this question, the answer is to call nextInt() on the Random: Collection.shuffle with seeded Random - anomaly with List of size 16

It feels like calling nextInt() before using the Random is just kicking the problem along the seed value for a while and again it will occur somewhere?

Does this answer your question? [Java random numbers using a seed](https://stackoverflow.com/questions/12458383/java-random-numbers-using-a-seed) — the Hutt, Mar 09 '21 at 03:33
@onkarruikar Thanks, but I want the Random to be deterministic dependent on the seed, so not sure that helps? — Steve Ford, Mar 09 '21 at 07:28

Sweeper · Answer 1 · 2021-03-09T04:02:14.507

You are just unlucky! The first positive seed that shuffles a non-3 to the last position is 256. Try this code yourself to find out the first 10 seeds that shuffles a non-3 to the last position.

public class Main {

  public static void main(String[] args) {
    IntStream.range(0, 1_000_000).filter(Main::lastPositionIsNot3).limit(10).forEach(System.out::println);
  }

  public static boolean lastPositionIsNot3(long seed) {
    List<Integer> consensusGroupOrder = new ArrayList<>();

    int numberOfItems = 4;
    for (int i = 0; i < numberOfItems; i++) {
      consensusGroupOrder.add(i + 1);
    }
    Collections.shuffle(consensusGroupOrder, new Random(seed));

    return consensusGroupOrder.get(3) != 3;
  }
}

For the seed 256, the order is 1, 3, 2, 4.

Note that shuffle guarantees "All permutations occur with equal likelihood assuming that the source of randomness is fair." Neither java.util.Random nor shuffle guarantee that there must be a pair of seeds, both of which below 256, that will shuffle lists in such a way that the last elements are different.

If you look at a larger sample size, e.g. all the seeds from 0 to 1 million, and count how many of those seeds does not produce 3 as their last element, you will get a more expected result:

long count = IntStream.range(0, 1_000_000).filter(Main::lastPositionIsNot3).count();
System.out.println(count);

This prints 750,404 for me. About 3 quarters of the seeds doesn't shuffle 3 to the end, which is expected. The actual number is 404 seeds (0.05%) more than what we expected. I would expect this percentage to go way lower, if you check the whole range of seeds (0 to 2^48-1) and count how many of those shuffles a non-3 to the end.

In short, The first 256 seeds is too small a sample size to say anything about the distribution of seeds.

thanks. not sure I fully understand, but suppose I wanted to create an even distribution using a range of say 100 contiguous seeds, would I just multiply the seed by something? — Steve Ford, Mar 09 '21 at 07:32
@SteveFord I think you need to realise just how many seeds there are - 2^48 of them! The first 256 seeds all shuffling a 3 to the last position can hardly be called "uneven". If you want 25 seeds to shuffle a 3 to the end, 25 to shuffle a 2 to the end, 25 to shuffle a 1 to the end, and 25 to shuffle a 4 to the end, then you should find such 100 seeds by trial and error. — Sweeper, Mar 09 '21 at 07:50
@SteveFord At that point, can you even call it "random" anymore? Why not just hardcode 100 permutations of [1,2,3,4], with exactly the distribution of permutations you want, and select from there? :) — Sweeper, Mar 09 '21 at 07:51

score 0 · Accepted Answer · answered Mar 09 '21 at 09:04

I just went with the author proposed work-around on Collection.shuffle with seeded Random - anomaly with List of size 16:

        List<Integer> consensusGroupOrder = new ArrayList<>();

        for (int i = 0; i < numberOfItems; i++) {
            consensusGroupOrder.add(i + 1);
        }

        Random r = new Random(seed);
        r.nextInt();

        Collections.shuffle(consensusGroupOrder, r);

        int count = 1;

        Map<Integer, Integer> returnValue = new HashMap<>();

        for(Integer group: consensusGroupOrder) {
            returnValue.put(count++, group);
        }

Java.util.Collection.Shuffle not producing random results when using a seeded Random

2 Answers2