How to randomize an array such that no element is in its original position

Question

I'm supposed to take an array of integers that starts from 0 and goes up to the length-1 of some other int array called cards (that has a user-inputted length) and completely randomize it such that no number is in its original position.
I figured out how to generate the first array, but I have absolutely no idea how to completely randomize an array, can anyone help? So far I have:

int size = cards.length;
int[] numberList = new int[size];
for (int i = 0; i < size; i++) {
    numberList[i] = i;
}

Update:

private int[] shuffleIndex() {
    int size = cards.length;
    int[] numberList = new int[size];
    for(int i = 0; i < size; i++) {
        numberList[i] = i;
    }
    randomizer(numberList);
    return numberList;
}
    
private int[] randomizer(int[] input) {
    
    int size = input.length;
    
    Random random = new Random();
    
    for (int i = size -1; i > 0; i--) {
        int j = random.nextInt(i + 1);
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
    
    for(int i = 0; i < size; i++) {
    
        if(input[i] == i) {
            randomizer(input);
        }
    }
    return input;
}

How do you prevent your randomization from getting the same element though? That's what I initially tried but it wasn't working. — GS1221, Nov 19 '21 at 22:04
@GS1221 - I suggest you add an explanation, why [`shuffle`](https://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#shuffle(java.util.List,%20java.util.Random)) from `Collections` would not suffice, to your question. — PM 77-1, Nov 19 '21 at 22:08
This answer is for C#, but you should be able to convert it to Java: https://stackoverflow.com/a/28740197/6395627. It essentially just repeats the [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) algorithm until the "no element at original position" condition is met. — Slaw, Nov 19 '21 at 22:09
I was told not to use ArrayLists on this assignment and from what I can tell, it looks like shuffle from Collections uses ArrayLists. I might have found a solution using the Fisher-Yates shuffle that some people were mentioning, do you mind checking it? I'll add it to the "So far I have" section in the original question — GS1221, Nov 19 '21 at 22:17
The algorithm in your update is a very effective one: for each entry linearly, swap it with a random other. That's the algorithm used by std::shuffle in most C++ standard library implementations. — Tim Roberts, Nov 19 '21 at 22:21
I understand the assignment says what it says, but I have to mention, the constraint "such that no number is in its original position" means that the result is not truly random. True randomness could, as unlikely as it is, result in an array that is exactly the same as the original array. This comment is, however, inconsequential to a solution. — Stephen P, Nov 19 '21 at 22:23
I completely agree, I'm not quite sure what I was thinking when I wrote it. Maybe something like "Each element would get moved to a separate place so it is completely different therefore completely random." Really bad logic on my part. — GS1221, Nov 19 '21 at 22:26
What do you do when the input is `[0]`? Your code throws `StackOverflowError`. — , Nov 19 '21 at 23:21
Does this answer your question? [Shuffle an array of strings so that the sting must be completely shuffled and not in its original index in Java](https://stackoverflow.com/questions/50146340/shuffle-an-array-of-strings-so-that-the-sting-must-be-completely-shuffled-and-no) — Peter O., Nov 20 '21 at 00:28

WJS · Answer 1 · 2021-11-20T00:42:38.060

Try it like this.

int size = cards.length;
int[] numberList = new int[size];
for (int i = 0; i < size; i++) {
    numberList[i] = i;
}
shuffle(numberList);
System.out.println(Arrays.toString(numberList));

If the array contained ints 1-12, this is an example of the output.

[7, 12, 1, 2, 8, 9, 6, 4, 11, 5, 10, 3]

Here is how it works.

start out with size set to array size
Iterate until size == 1
grab the last element in the array
generate a random position exclusive of the value of size to move it to
swap that element with the one in the last position.
decrement the size to preserve the new last element. The next call to nextInt() will not touch it since it was decremented.
since the random number generated is exclusive of the position to be swapped no element will ever occupy its original position.

public static void shuffle(int[] arr) {
    Random r = new Random();
    int size = arr.length;
    while (size-- > 1) {
        int item = r.nextInt(size);
        int t = arr[size];
        arr[size] = arr[item];
        arr[item] = t;
    }
}

How to randomize an array such that no element is in its original position

1 Answers1