Unrepated random numbers

**merik** · 12-07-2010, 04:24 AM

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.

**pbrockway2** · 12-07-2010, 04:56 AM

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