在Java中均匀地生成随机排列 [英] Generating Random Permutation Uniformly in Java

问题描述

任何人都知道一种快速/最快的方法来生成Java中整数列表的随机排列.例如，如果我想要一个长度为5的随机排列，答案将是1 5 4 2 3，其中每个5!可能性都是同等的可能性.

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.

我对如何解决此问题的想法是运行一种方法，该方法在所需长度的数组中生成随机实数，然后对它们进行排序以返回索引，即0.712 0.314 0.42 0.69 0.1将返回5 2 3 4 1的排列.我认为这可以在O(n^2)中运行，目前我的代码大约在O(n^3)中运行，并且这在当前程序的运行时间中占很大比例.从理论上讲，这似乎还可以，但我在实践中不确定.

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

推荐答案

如果目的仅仅是生成随机排列，我真的不了解排序的必要性.据我所知，以下代码在线性时间内运行

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

下面是一些测试代码:

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

这篇关于在Java中均匀地生成随机排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！