Java - Shuffle a specific number of elements in an array

Question

My problem is the following: I need to shuffle an array and then get just the first N elements. I am currently shuffling the whole array, that has 50+ elements, but this gives me performance problems, since the shuffling routine is called 1e+9 times. I am currently implementing the Fisher-Yates algorithm to shuffle: ``` public static void shuffle(int[] array) { Random gen = new Random(); for (int i = array.length - 1; i > 0; i--) { int index = gen.nextInt(i + 1); int a = array[index]; array[index] = array[i]; array[i] = a; } } ``` Then I select just the first N elements. I have also tried using Reservoir sampling, but it just saved me 1 second. That's not enough, since my program runs for 30 secs. Also, I might have implemented it incorrectly, because I am not getting the same results when compared to the Fisher-Yates algorithm. This is my implementation: ``` public static int[] shuffle(int[] array, int N) { int[] ret = new int[N]; for (int i = 0; i < N; i++) { ret[i] = array[i]; } Ra…

Accepted Answer

A simple way to get `N` shuffled elements from the array is as follows:

- Pick a random element `r`.

- Add element `r` to the output.

- Move the last element of the array to the position of `r` and shrink the array size by 1.

- Repeat `N` times.

In code:

```
public static int[] shuffle(int[] array, int N) {
    int[] result = new int[N];
    int length = array.length;

Random gen = new Random();

for (int i = 0; i < N; i++) {
        int r = gen.nextInt(length);

result[i] = array[r];

array[r] = array[length-1];
        length--;
    }

return result;
}
```

This algorithm has the advantage over FY that it only computes the first `N` elements of the shuffled array, rather than shuffling the whole array.

Your optimized algorithm is not optimal for two reasons:

- The first `N` elements are never shuffled. For instance, element 0 can never appear at position 1 in the shuffled array.

- You're still doing a lot of work. If `N=10` and the total array length is `1000000`, you're still computing about `1000000` random values, while you only need `10`.

Java - Shuffle a specific number of elements in an array

Solution

Problem

Related problems