用Java统一生成随机置换
任何人都知道在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)运行，并且此时我的程序的运行时间占很大比例。 从理论上讲，这似乎没问题但我在实践中并不确定。
如果目的只是生成一个随机排列，我真的不明白排序的必要性。 就我所知，以下代码以线性时间运行
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 counts = new ArrayList (); // filled with Integer ArrayList arrays = new ArrayList (); // 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}); }
你试过以下吗？
Collections.shuffle(list)
这将迭代每个元素，使用随机剩余元素交换该元素。 这具有O（n）时间复杂度。
有一种易于实现的O（n） Shuffle方法。
只需生成0到n! - 1之间的随机数n! - 1 n! - 1并使用
我在别处提供的算法（通过其排名生成排列） 。