Generating Random Permutation Uniformly in Java

Anyone know of a fast/the fastest way to generate a random permutation of a list of integers in Java. For example if I want a random permutation of length five an answer would be 1 5 4 2 3, where each of the 5! possibilities is equally likely.

My thoughts on how to tackle this are to run a method which generates random real numbers in an array of desired length and then sorts them returning the index i.e. 0.712 0.314 0.42 0.69 0.1 would return a per开发者_StackOverflow社区mutation of 5 2 3 4 1. I think this is possible to run in O(n^2) and at the moment my code is running in approximately O(n^3) and is a large proportion of the running time of my program at the moment. Theoretically this seems OK but I'm not sure about it in practice.

Have you tried the following?

Collections.shuffle(list)

This iterates through each element, swapping that element with a random remaining element. This has a O(n) time complexity.

If the purpose is just to generate a random permutation, I don't really understand the need for sorting. The following code runs in linear time as far as I can tell

public static int[] getRandomPermutation (int length){

    // initialize array and fill it with {0,1,2...}
    int[] array = new int[length];
    for(int i = 0; i < array.length; i++)
        array[i] = i;

    for(int i = 0; i < length; i++){

        // randomly chosen position in array whose element
        // will be swapped with the element in position i
        // note that when i = 0, any position can chosen (0 thru length-1)
        // when i = 1, only positions 1 through length -1
                    // NOTE: r is an instance of java.util.Random
        int ran = i + r.nextInt (length-i);

        // perform swap
        int temp = array[i];
        array[i] = array[ran];
        array[ran] = temp;
    }                       
    return array;
}

And here is some code to test it:

public static void testGetRandomPermutation () {

    int length =4;  // length of arrays to construct

    // This code tests the DISTRIBUTIONAL PROPERTIES
    ArrayList<Integer> counts = new ArrayList <Integer> ();  // filled with Integer
    ArrayList<int[]> arrays = new ArrayList <int[]> ();  // filled with int[]

    int T = 1000000; // number of trials
    for (int t = 0; t < T; t++) {           
        int[] perm = getRandomPermutation(length);
        // System.out.println (getString (perm));
        boolean matchFound = false;
        for(int j = 0; j < arrays.size(); j++) {
            if(equals(perm,arrays.get(j))) {
                //System.out.println ("match found!");
                matchFound = true;
                // increment value of count in corresponding position of count list
                counts.set(j, Integer.valueOf(counts.get(j).intValue()+1));
                break;
    }                       
        }
        if (!matchFound) {
            arrays.add(perm);
            counts.add(Integer.valueOf(1));
        }   
    }

    for(int i = 0; i < arrays.size(); i++){
        System.out.println (getString (arrays.get (i)));
        System.out.println ("frequency: " + counts.get (i).intValue ());
    }

    // Now let's test the speed
    T = 500000;  // trials per array length n       
    // n will the the length of the arrays
    double[] times = new double[97];
    for(int n = 3; n < 100; n++){
        long beginTime = System.currentTimeMillis();
        for(int t = 0; t < T; t++){
            int[] perm = getRandomPermutation(n);
        }
        long endTime = System.currentTimeMillis();
        times[n-3] = (double)(endTime-beginTime);
        System.out.println("time to make "+T+" random permutations of length "+n+" : "+ (endTime-beginTime));
    }
    // Plotter.plot(new double[][]{times});     
}

There is an O(n) Shuffle method that is easy to implement.

Just generate random number between 0 and n! - 1 and use
the algorithm I provided elsewhere (to generate permutation by its rank).