Java permutations with least random numbers possible

Question

I want to generate a permutation of an array a and I don't want to use utility functions such as java.util.Collections().
The permutations should be randomized and every permutation should be possible to occur - but there is no need for an equally distributed probability.

The following code achieves this - but at poor performance :

// array holding 1,...,n
// initialized somewhere else
int[] a = new int[N];

for (int i = 0; i < a.length ; i++) {
     int r = (int) (Math.random() * (i+1));     
     swap(r,i,a);
  }

private static void swap(int j, int k, int[] array){
      int temp = array[k];
      array[k] = array[j];
      array[j] = temp;
}

Question:
Is there any chance of reducing the total number of random numbers used for the generation of a permutation?

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).