1. Member
Join Date
Nov 2010
Posts
12
Rep Power
0

## 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.

2. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
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.

Java 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)

Java 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

3. Member
Join Date
Nov 2010
Posts
12
Rep Power
0
Thanks for your reply. I was actually looking for an in-place shuffle. I just didn't know the name of it!

4. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
You're welcome. It is also known as a Fisher-Yates shuffle. Wikipedia has an article under that name.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•