Is java.util.Random really that random? How can I generate 52! (factorial) possible sequences?

Question

I've been using Random (java.util.Random) to shuffle a deck of 52 cards. There are 52! (8.0658175e+67) possibilities. Yet, I've found out that the seed for java.util.Random is a long, which is much smaller at 2^64 (1.8446744e+19).

From here, I'm suspicious whether java.util.Random is really that random; is it actually capable of generating all 52! possibilities?

If not, how can I reliably generate a better random sequence that can produce all 52! possibilities?

"how can I surely generate a real random number over 52!" The numbers from Random are never real random numbers. It's a PRNG, where P stands for "pseudo." For real random numbers, you need a source of randomness (such as random.org). — T.J. Crowder
@JimGarrison That is not what OP's after. He's talking about 10^68 possible sequences. Since each pseudo-random sequence is identified by its seed, OP says there could be at the most 2^64 different sequences. — Sergey Kalinichenko
I think it's an interesting question, and is worth thinking about. But I can't help wondering about your problem context: what it is exactly that's leading to the requirement to be able to generate all 52! permutations? For example, in real-world bridge we can shuffle the deck and deal one card at a time, yet there are only ~6e11 different hands since many different permutations result in the same hand. Thinking in the other direction, do you need a solution specifically for 52!, or do you need one that generalizes to, say, two decks shuffled together (104!/(2**52) possibilities, or ~2e150)? — NPE
@NPE - Take Solitaire (Klondike) for instance, 52! is exactly the number of possible hands.. — Sergei Emelianov

NPE NPE · Accepted Answer · 2018-08-09T16:43:24

Selecting a random permutation requires simultaneously more and less randomness than what your question implies. Let me explain.

The bad news: need more randomness.

The fundamental flaw in your approach is that it's trying to choose between ~2²²⁶ possibilities using 64 bits of entropy (the random seed). To fairly choose between ~2²²⁶ possibilities you're going to have to find a way to generate 226 bits of entropy instead of 64.

There are several ways to generate random bits: dedicated hardware, CPU instructions, OS interfaces, online services. There is already an implicit assumption in your question that you can somehow generate 64 bits, so just do whatever you were going to do, only four times, and donate the excess bits to charity. :)

The good news: need less randomness.

Once you have those 226 random bits, the rest can be done deterministically and so the properties of java.util.Random can be made irrelevant. Here is how.

Let's say we generate all 52! permutations (bear with me) and sort them lexicographically.

To choose one of the permutations all we need is a single random integer between 0 and 52!-1. That integer is our 226 bits of entropy. We'll use it as an index into our sorted list of permutations. If the random index is uniformly distributed, not only are you guaranteed that all permutations can be chosen, they will be chosen equiprobably (which is a stronger guarantee than what the question is asking).

Now, you don't actually need to generate all those permutations. You can produce one directly, given its randomly chosen position in our hypothetical sorted list. This can be done in O(n²) time using the Lehmer^[1] code (also see numbering permutations and factoriadic number system). The n here is the size of your deck, i.e. 52.

There is a C implementation in this StackOverflow answer. There are several integer variables there that would overflow for n=52, but luckily in Java you can use java.math.BigInteger. The rest of the computations can be transcribed almost as-is:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] Not to be confused with Lehrer. :)

Is java.util.Random really that random? How can I generate 52! (factorial) possible sequences?

9 Answers