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

Answer 3

有一个 O(n) Shuffle 方法很容易实现。

Answer 4

只需生成 0 和 n 之间的随机数即可！ - 1 并使用
我在其他地方提供的算法（通过以下方式生成排列）它的排名）。