1

When using a Random seed that increments by 1 (e.g. epochDay) to generate a deterministic shuffling for a List, I'm observing that for some sequence of the seed a certain entry will always be on the last position of the result.

This only happens for Collections of size 16.

I've narrowed it down to this piece of code:

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

public class Main {

    public static void main(String[] args) {

        for (int i = 0; i < 50; i++) {
            List<String> values = Arrays.asList(
                "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
                "A", "B", "C", "D", "E", "F"
            );

            Random r = new Random(i);
            Collections.shuffle(values, r);
            System.out.println(values);
        }
    }
}

which produces the following output:

[0, 7, C, 9, 6, 5, A, 4, 3, 1, 2, E, 8, F, D, B]
[A, 5, 0, C, 3, 8, 6, 7, E, 4, F, 2, 9, 1, D, B]
[D, 5, 7, E, A, 2, 3, F, 0, 6, 1, 9, 8, 4, C, B]
[4, F, 8, E, A, 3, D, 1, C, 9, 2, 0, 7, 6, 5, B]
[E, 6, A, 5, F, 2, 8, 0, C, D, 4, 3, 9, 1, 7, B]
[2, 9, 0, 1, C, F, 5, 3, 8, D, E, 6, A, 4, 7, B]
[5, F, 0, D, 3, A, 8, 2, C, 7, 4, 1, 9, E, 6, B]
[3, C, 1, 6, 2, 0, 7, 9, 5, 8, D, 4, A, F, E, B]
[3, 9, 2, A, 5, 6, F, D, 8, E, 7, 0, C, 4, 1, B]
[0, D, 4, 5, E, 2, A, 7, 6, 3, 9, C, F, 8, 1, B]
[2, 5, E, 3, 8, D, 1, 6, 4, C, 7, A, F, 9, 0, B]
[C, 3, 5, A, 6, E, 4, 1, 2, 0, 7, 9, F, D, 8, B]
[F, 7, 3, D, 8, E, C, 9, 5, 0, A, 4, 1, 6, 2, B]
[8, 0, 5, D, E, 6, 4, 9, 2, 3, C, 7, 1, F, A, B]
[5, 4, 7, A, 1, 3, 0, 8, F, 6, E, 2, C, D, 9, B]
[8, C, 6, 4, D, F, 3, 5, 7, 9, A, 1, 0, E, 2, B]
[9, F, A, 4, 0, 6, E, 8, 5, 3, 2, C, 1, D, 7, B]
[8, 5, 9, A, 7, 6, 1, E, 3, F, C, D, 2, 4, 0, B]
[9, D, 5, 6, C, A, 3, 7, 2, 8, 0, F, 1, 4, E, B]
[D, 3, 1, 6, 5, 4, 7, F, 9, C, 2, A, 0, 8, E, B]
[6, 8, 0, 7, A, C, 4, D, 9, 3, F, 5, 2, E, 1, B]
[2, 7, 1, D, C, A, 0, E, F, 4, 5, 8, 3, 6, 9, B]
[D, A, 9, 5, 1, 6, 4, F, E, 7, C, 3, 2, 8, 0, B]
[E, 7, A, C, 2, 9, 1, D, 5, 0, 4, 6, 3, F, 8, B]
[9, E, 8, D, 4, 0, 3, C, 1, F, 7, 2, 5, 6, A, B]
[D, A, C, F, E, 2, 8, 0, 6, 5, 7, 1, 4, 9, 3, B]
[A, 0, C, 2, D, 1, 3, E, 6, 7, 5, 8, 4, F, 9, B]
[D, 5, A, 9, C, 3, 6, 8, E, 0, 7, F, 4, 1, 2, B]
[F, 5, 1, E, D, 3, 9, 0, C, 2, A, 6, 7, 8, 4, B]
[C, 9, 1, 2, 6, 8, 0, 3, E, F, A, 5, 7, D, 4, B]
[1, 0, 9, C, 8, 7, 2, E, F, 6, A, 4, 5, D, 3, B]
[E, 2, 8, C, D, 1, 7, 5, 0, 9, A, 3, 6, 4, F, B]
[4, 2, 6, F, C, 8, 5, A, E, 0, 3, 7, D, 9, 1, B]
[0, 5, E, 7, 4, 2, 1, 6, 8, F, 3, C, A, D, 9, B]
[0, 9, 3, 2, 4, A, E, F, C, 6, 1, 5, 7, D, 8, B]
[D, F, 2, 6, 9, A, 1, 0, 5, 7, 3, C, E, 4, 8, B]
[2, 5, 4, 0, 1, C, D, 7, 8, 9, 6, 3, E, F, A, B]
[7, A, 8, E, 1, 5, 0, 9, 4, C, 6, D, F, 2, 3, B]
[7, 3, D, 0, C, 9, A, F, 5, 6, 4, 1, 8, E, 2, B]
[5, 3, 7, E, C, 8, F, 4, 1, A, D, 0, 9, 6, 2, B]
[C, 5, 1, 2, 7, 0, E, 3, 6, A, 9, 8, F, D, 4, B]
[7, 8, 5, 0, D, 3, 1, 6, A, 2, 9, F, E, 4, C, B]
[F, 4, 0, 1, 7, A, E, 9, 2, 5, 8, D, C, 6, 3, B]
[1, C, 7, 3, 2, 4, 6, 0, 9, A, 8, 5, D, E, F, B]
[1, A, 2, 5, 6, E, 9, 7, 3, 8, F, C, 0, 4, D, B]
[7, F, 5, D, 4, 8, E, 2, A, 1, C, 3, 0, 9, 6, B]
[7, 3, 8, 2, 6, D, 4, 1, F, 5, E, A, 0, 9, C, B]
[2, 9, 7, F, 3, 6, A, 4, E, 8, 0, C, 1, D, 5, B]
[7, 6, 1, D, 8, 5, 0, 4, A, C, 3, 9, 2, E, F, B]
[5, A, 1, F, 6, 2, 9, 7, 8, C, 4, 0, E, D, 3, B]

(Tested on Oracle JRE 1.8, 10 and 12)

As you can see, the entry B always ends up in the last position of the list. When I let the seed run to values in other ranges, a different element will be placed last, but always the same one for an interval 100-300 incremental seed values.

I can work around the issue by placing a call to r.nextInt() before the shuffle, however I'm still baffled by this behaviour and would like to know if there is an explanation or documentation for it.

Philip Frank
  • 225
  • 3
  • 5

1 Answers1

1

the source codeshuffle(List<?> list, Random rnd)

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));
        } else {
        ...

so the problem is random.nextInt(16) always return 11

and Random.java

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

public Random(long seed) {
    if (getClass() == Random.class)
        this.seed = new AtomicLong(initialScramble(seed));
    else {
        // subclass might have overriden setSeed
        this.seed = new AtomicLong();
        setSeed(seed);
    }
}

private static long initialScramble(long seed) {
    return (seed ^ multiplier) & mask;
}

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);

    int r = next(31);
    int m = bound - 1;
    if ((bound & m) == 0)  // i.e., bound is a power of 2
        r = (int)((bound * (long)r) >> 31);
    else {
        for (int u = r;
             u - (r = u % bound) + m < 0;
             u = next(31))
            ;
    }
    return r;
}

the first call of random.nextInt(16)

int bound = 16;
long seed = (i ^ multiplier) & mask;
long r = (seed * multiplier + addend) & mask;
r = (r >>> (48 - 31));
r = (bound * r) >> 31;

after simplify

//j is in [-64, 64]
r = (((multiplier + j) * multiplier + addend) >>> 44) & 0xF

and multiplier < (1 << 35), so

r = ((multiplier * multiplier) >> 44) & 0xF

that is 11

Ivan Young
  • 329
  • 2
  • 6