A quiz app shuffles twenty questions with Collections.shuffle. A home-grown version does sort by Random.nextDouble(). Another swaps i with nextInt(n) for every i — including indexes already passed. Both compile. The first is extra memory and a worse RNG story. The second biases some permutations: later slots get more chances to be swapped.

Fisher-Yates (Knuth): for i from n−1 down to 1, swap a[i] with a[j] where j is uniform in 0..i inclusive. Every permutation has probability 1/n!. In-place. O(n) swaps. That is the JDK map entry for shuffle.

This post is that loop. Sampling k of an unknown stream is Reservoir Sampling. Catalog: Algorithms Roadmap. It is not a CSPRNG lecture. Do not hand-roll crypto shuffles.

The biased swap

static void biased(int[] a, Random r) {
    for (int i = 0; i < a.length; i++) {
        int j = r.nextInt(a.length); // 0..n-1 every time
        swap(a, i, j);
    }
}

Index 0 can be swapped away on every later i. Index n-1 is only swapped on the last iteration as i, but can still be chosen as j throughout. Counts of permutations are not equal. Tests with n = 3 already show it if you histogram.

Sort-by-random-key is unbiased if the keys never tie and the sort is not broken by double collisions. It allocates, and it is not what you wanted to type.

The prefix that is already done

After the swap at i, a[i] is a uniformly chosen remaining element, and a[i+1..] is a uniform shuffle of what was left. Induction down to i = 1.

static void shuffle(int[] a, Random r) {
    for (int i = a.length - 1; i > 0; i--) {
        int j = r.nextInt(i + 1); // 0..i inclusive
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

Collections.shuffle(list) is this algorithm on a List (with a Random you can pass). Arrays has no public shuffle; wrap as List or write the loop on T[].

Forward form (i from 0 to n-2, j in i..n-1) is the same permutation distribution. Pick one and keep j inside the unshuffled suffix (or prefix).

Note: ThreadLocalRandom / RandomGenerator is fine for games and tests. Do not use this Random to shuffle cryptographic keys. SecureRandom still needs a reason; shuffling a password list is not encryption.

Partial shuffle: first k of a random permutation

You only need k random winners from n, order among winners uniform.

static void partialShuffle(int[] a, int k, Random r) {
    for (int i = 0; i < k; i++) {
        int j = i + r.nextInt(a.length - i);
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

Prefix a[0..k) is a uniform random subset in random order. That is not reservoir sampling: here n is known and the array is already in RAM.

When not to use Fisher-Yates

  • n unknown, one pass. Reservoir Sampling.
  • You needed a random sample without shuffling the rest. Partial shuffle above, or a hash set of picks.
  • Crypto-grade permutation of secret material. Use a vetted API, not java.util.Random.

Cheat sheet

Job:       uniform random permutation, in place
Loop:      i = n-1 .. 1; j = nextInt(i+1); swap(i,j)
Why:       P(each perm) = 1/n!
JDK:       Collections.shuffle(list [, Random])
Partial:   first k swaps with j in i..n-1
Not this:  sort-by-double; swap with nextInt(n) every i; reservoir (unknown n)

Do:

  • Draw j from the remaining suffix (or prefix), inclusive.
  • Call Collections.shuffle in application code.
  • Pass a Random in tests so the shuffle is repeatable.

Don’t:

  • Swap i with nextInt(n) for every i and call it fair.
  • Sort by Math.random() as a default shuffle.
  • Use java.util.Random as a CSPRNG.

Wrap-up

Fisher-Yates makes the next position a uniform draw from what is left, then never touches it again. That is the unbiased in-place shuffle. The JDK already runs it. The biased “swap with any index” loop is the interview trap.

When n is not known up front and the items arrive as a stream, the fair sample is a different pass: reservoir sampling.

Next optional step in the series One-pass sample when you do not know n up front. Reservoir Sampling: One Pass When You Do Not Know n Up Front