Java permutations with least random numbers possible

Answer 1

I'll be surprised if anyone improves on the Knuth shuffle. It's O(n).

It takes O(n) random numbers, which is not sufficient for me.

This citation claims an O(n log n) algorithm.

We'd all love to see see O(log n) or O(1).

O(log n) algorithms usually depend on "divide and conquer" bisection, which brings to mind cutting the deck and dividing each half.

But I can't help but think that if a faster algorithm were accessible Knuth would have found it.

Answer 2

The only possible optimization I can think of is making the random number generator faster. An easy solution is to generate random ints in the first place:

import java.util.Random;
Random rand = new Random();

for (int i = 0; i < a.length ; i++) {
    swap(rand.nextInt(i+1), i, a);
}

...

Alternatively, you can invent a faster way to generate more or less random numbers (uniformly distributed or not, suited to your needs). However, there's no way you can overcome the O(n) limitation.

Answer 3

A sequence of length n has n! permutations. If each permuation needs to be possible, there must be a possible sequence of random numbers for each one.

To randomly permute an array of length n, you can therefore generate a single random number from the range 1..n! uniformly at random. This identifies a single permutation, which you can then apply.

You might improve your question to ask how many random bits are needed. By the same argument, that will be log(n!). To give you an idea about the asymptotic behaviour of that function, consider:

Let n > 3:

n = log(2^n) < log(n!) < log(n^n) = n * log(n)

So n random bits can not be enough (for n > 3). In fact, one can prove that log(n!) is not in O(n).