自定义混洗算法

Question

我知道有一种高效的洗牌算法，我相信它叫Fisher Yates，但我试图构建一个自定义的算法(出于固执(。

我试图在正确的范围内生成一个新的随机数，然后用它来确定复制数组中的一个新随机位置。然后存储这个随机数以避免使用两次。我的方法不起作用。有人愿意给我一些启发吗？

public int[] shuffled(int[] numbers) {
int rand;
int copyNumbers[] = new int[numbers.length];
int usedRand[] = new int[numbers.length];

for (int i = 0; i < numbers.length; i++) {
rand = new Random().nextInt(numbers.length + 1);
if ((i != rand) && (usedRand[i]!=rand)) {
copyNumbers[rand] = numbers[i];
usedRand[i]=rand;
}
}
numbers = copyNumbers;
return numbers;
}

Answer 1

因为我已经在注释中指出了错误。以下是shuffle((的可能实现。我根据自己的修改对代码进行了注释。如果你碰巧有问题，请随时提问！

public static void main(String[] args) {
//sample values
int[] numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18};
//First call of recursive function
int[] x = shuffled(numbers, null, null, false, 0);
//Print out values
for (int i = 0; i < x.length; i++) {
System.out.print(x[i] + "|");
}
}
public static int[] shuffled(int[] numbers, int usedRand[], int[] copyNumbers, boolean newRandomValue, int current) {
//Initialisation
int rand = -1;
int start = 0;
//If function hasn't been called before, initialise.
if (usedRand == null) {
usedRand = new int[numbers.length];
Arrays.fill(usedRand, -1);
}
if (copyNumbers == null) {
copyNumbers = new int[numbers.length];
}
//If function has been called recursively, reassign the start-Integer for for-loop
if (newRandomValue) {
start = current;
}
//Iterate over numbers-array with <start> as start-index
for (int i = start; i < numbers.length; i++) {
/*
new Random().nextInt(numbers.length+1 ) gets a random number between 0 and numbers.length + 1
In our example, numbers.length+1 is 20. So we will get a random number between 0 and 20. 
But we want to get random values between -1 and 19, so 
new Random().nextInt(numbers.length+1 ) --> values between 0 to 20
rand = new Random().nextInt(numbers.length+1 ) -1  --> values between -1 to 19
*/
rand = new Random().nextInt(numbers.length+1 ) -1;
//Iterate through usedRand array and compare if current rand value has already been used yet.
for (int j = 0; j < usedRand.length; j++) {
if (usedRand[j] == rand) {
/*
If current rand value has already been used, recursively call shuffle again with the current index i
as new start-index
*/
return shuffled(numbers, usedRand, copyNumbers, true, i);
}
}
copyNumbers[rand] = numbers[i];
usedRand[i] = rand;
}
numbers = copyNumbers;
return numbers;
}