How do I generate a random derangement of a list/array in java?

Question

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]

Usually the easiest way to do this is to create a `List` of the numbers in order, and then just shuffle it — GBlodgett, Mar 28 '19 at 17:35
Not an exact duplicate, but worth look at: https://stackoverflow.com/q/20058366/2422776 — Mureinik, Mar 28 '19 at 17:36
If you still want to use an `Array` look at [this](https://stackoverflow.com/questions/1519736/random-shuffling-of-an-array) thread — GBlodgett, Mar 28 '19 at 17:39
A derangement is a random permutation. The well-known method for producing one is a [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) which also appears in Knuth, D. "The Art of Computer Programming" Vol. 2, Seminumerical Algorithms. — David Conrad, Mar 29 '19 at 15:05
It's not just a random permutation; it is one where no element is in its original position. — Jon, Mar 29 '19 at 15:45

score 0 · Answer 1 · answered Mar 28 '19 at 17:55

The idea would be to have N elements inside a collection and you would pick numbers out of it until it is depleted. Something like this

List<Integer> temp = IntStream.range(0, 6).boxed().collect(Collectors.toList());
int[] array = new int[6];
while (temp.size() > 0) {
    int rndIndex = ThreadLocalRandom.current().nextInt(temp.size());
    array[temp.size() - 1] = temp.get(rndIndex);
    temp.remove(rndIndex);
}
System.out.println(Arrays.toString(array)); // could be [4, 5, 3, 2, 1, 0]

If you don't want to use a temporary List, you could do so, but that would require more code. The idea would be the same.

I did that already... without a list. Just got voted down when i posted it before any other answers. — Mr00Anderson, Mar 28 '19 at 17:56

score -1 · Accepted Answer · answered Mar 28 '19 at 17:50

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.

How do I generate a random derangement of a list/array in java?

2 Answers2