How to get unique random items from an array?

问题:

Hey there,
I have an array of (unique) objects and would like to get 4 random objects of this array, but the same object shouldn't be fetched twice, so using a simple random function won't work.

I had two ideas:
1. Shuffle the array and get the first 4 items. -> Overhead, because the array can be very large.
2. Generate a random index. If that index was used before, try again, and so on... -> Somewhat unreliable...

Do you know a better, more efficient method?

回答1:

Shuffle the array and get the first 4 items. -> Overhead, because the array can be very large.

Use the modern version of the Fisher Yates shuffle. It can be performed in-place and if you stop after the first four swaps it will give you the result you need. There is no need to shuffle the entire array.

Compared to some other solutions, it also has the advantage that, if only part of the resulting permutation is needed, it can be stopped halfway through