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

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?

Solution

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^{226} possibilities using 64 bits of entropy (the random seed). To fairly choose between ~2^{226} 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^{2}) 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. :)

- Maven (commandline): No compiler is provided in this environment
- Java Swing: display Text selectable
- How to make a query for mongodb using spring to return objects ordered alphabetically'
- cant update array contents java
- In Gradle, how can I generate a POM file with dynamic dependencies resolved to the actual version used?
- Why do we use @Embeddable In Hibernate
- IS there a way to configure ehcache 2 for spring boot 3?
- org.hibernate.mapping.Table.getColumn returns null
- Java Swing bars floating instead of starting from the same baseline
- How to find files that match a wildcard string in Java?
- java.lang.ClassCastException: oracle.sql.CLOB cannot be cast to oracle.sql.CLOB
- Update a Vertex after Retrieving it
- Read nested list with other attributes in Java streams
- Do you not need a password to access a truststore (made with the java keytool)?
- Creating new Instance of @Component each time FXMLLoader calls applicationContext.getBean(class)
- Add ' to particular place in String in Java
- ExecutionCompletionService hangs when used with Project loom
- How do you handle "impossible" exceptions in Java?
- Android navigation drawer, change text/hover color
- Fastest way to determine if an integer's square root is an integer
- Play WAV file backward
- EclipseLink and Derby with Java 19
- SpringBoot + AWS cognito, can't resolve issuerUri
- Is there a way to use a custom, arbitrary SQL query for loading an entity in Jmix?
- Fill an array with matches from a HashMap in Java
- Print retry count with @Retryable
- Actuator endpoints returning 500 error after upgrade to spring boot 3
- Bufferedimage resize
- What is the difference between ExecutorService.submit and ExecutorService.execute in this code in Java?
- Spring Boot - Process finished with exit code 0