# Unrepated random numbers

• 12-07-2010, 04:24 AM
merik
Unrepated random numbers
I want to get a randomly sorted list of integers between 0 and n, and I want each value to appear only once. Also, I want it to be performed efficiently -- preferably in O(NlogN) rather than O(N2).

The original idea I had was to create an array of size n, use Random's nextInt(arr.length) to get an index in the array, return the value at that index, and then remove that element from the array (by shifting remaining cells to the left and reducing the array size by one). However, this takes O(N2).

Any suggestion with example code is appreciated.
• 12-07-2010, 04:56 AM
pbrockway2
You don't say it but your algorithm is picking a random index from a range that's getting smaller and smaller as the array elements get chosen.

Code:

```1  2  3  4  5  6  7  8       ^                    3 1  2  4  5  6  7  8               ^          3  7 1  2  4  5  6  8   ^                      3  6  2 1  4  5  6  8 etc```

It's all of those shifts that are taking time and effort. (10 in the example above to get the first three numbers.)

Consider a minor variation without the shifting. (The random index is chosen as before, but now it's swapped with the end of the array)

Code:

```1  2  3  4  5  6  7  8       ^                  (swap 3 with end==8) 1  2  8  4  5  6  7  [i]3[/i]               ^          (swap 6 with end==7) 1  2  8  4  5  7  [i]6  3[/i]   ^                      (swap 2 with end==7) 1  7  8  4  5  [i]2  6  3[/i]```

It's a standard inplace shuffle as used by java.util
• 12-11-2010, 10:18 PM
merik
Thanks for your reply. I was actually looking for an in-place shuffle. I just didn't know the name of it!
• 12-12-2010, 12:02 AM
pbrockway2
You're welcome. It is also known as a Fisher-Yates shuffle. Wikipedia has an article under that name.