I am having trouble implementing a method that returns a random derangement of size n. I am not sure what is wrong with my code, and I need help figuring out what's logically wrong.
This is for a small program I just wanted to write but having trouble visualizing the logic flow. I have tried changing the conditions of the while loop but nothing I tried works so far. I also tried implementing by using a list and arraylist but it became a bit too complex when I tried to put it into code.
Is there a simpler way to do this?
public static int[] derangement(int n){
int[] arr1 = new int[n];
int[] arr2 = new int[n];
//second array is to keep track of which positions are 'taken' to prevent collision
Random rand = new Random();
int temp = -1;
for(int i =0; i <n; i++){
arr1[i] = i;
}
for(int k=0;k<n;k++){
arr2[k] = -1;
}
for(int j=0;j<n;j++){
temp = j;
while (temp == j || arr2[j] != -1){
temp = rand.nextInt(n); //generate a random number until it gives one that hasn't been used before
if(arr2[temp] == -1){
arr2[temp] = j;
}
}
}
return arr2;
}
I expected the output as [2,4,1,5,3,0] for n = 6, but I just get [-1,-1,-1,-1,-1,-1]
What about using a SortedMap where your keys are going to be random, like this:
public static int[] derangement(int n){
Random rand = new Random();
int[] result = new int[n];
SortedMap<Double, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++) {
map.put(rand.nextDouble(), i);
}
int i = 0;
for (Double key: map.keySet()) {
result[i] = map.get(key);
i++;
}
return result;
}
This way, as the random keys in your map become ordered, you are shuffling the list.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments