Генерация случайной перестановки равномерно в Java

Question

Любой знает быстрый / самый быстрый способ генерирования случайной перестановки списка целых чисел в Java.Например, если я хочу случайную перестановку длины пять, ответом будет 1 5 4 2 3, где каждая из 5! возможностей одинаково вероятна.

Мои мысли о том, как решить эту проблему, состоят в том, чтобы запустить метод, которыйгенерирует случайные действительные числа в массиве желаемой длины, а затем сортирует их, возвращая индекс, т.е. 0.712 0.314 0.42 0.69 0.1 вернул бы перестановку 5 2 3 4 1.Я думаю, что это возможно для запуска в O(n^2), и в данный момент мой код работает примерно в O(n^3) и составляет большую часть времени выполнения моей программы в данный момент.Теоретически это выглядит нормально, но я не уверен в этом на практике.

Answer 1

Вы пробовали следующее?

Collections.shuffle(list)

Это повторяет каждый элемент, заменяя этот элемент случайным оставшимся элементом.Это имеет O (n) временную сложность.

Answer 2

Если цель состоит в том, чтобы просто сгенерировать случайную перестановку, я не очень понимаю необходимость сортировки. Насколько я могу судить, следующий код выполняется за линейное время

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;
}

А вот код для его проверки:

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});     
}

Answer 3

Существует метод O (n) Shuffle , который легко реализовать.

Answer 4

Просто сгенерируйте случайное число между 0 и n! - 1 и используйте
алгоритм, который я предоставил в другом месте (для генерации перестановки по его рангу) .