用Java统一生成随机置换

Question

任何人都知道在Java中生成整数列表的随机排列的快速/最快方法.例如,如果我想要一个长度为5的随机排列,那么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});     
}