Results 1 to 4 of 4
  1. #1
    merik is offline Member
    Join Date
    Nov 2010
    Posts
    12
    Rep Power
    0

    Default 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. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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. #3
    merik is offline Member
    Join Date
    Nov 2010
    Posts
    12
    Rep Power
    0

    Default

    Thanks for your reply. I was actually looking for an in-place shuffle. I just didn't know the name of it!

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    You're welcome. It is also known as a Fisher-Yates shuffle. Wikipedia has an article under that name.

Similar Threads

  1. Replies: 8
    Last Post: 04-19-2009, 05:50 PM
  2. Help with random numbers
    By checkmylongboarding in forum New To Java
    Replies: 2
    Last Post: 01-12-2009, 05:47 AM
  3. Random numbers
    By jithan in forum Advanced Java
    Replies: 3
    Last Post: 06-14-2008, 02:04 PM
  4. random numbers without random class`
    By carlos123 in forum New To Java
    Replies: 4
    Last Post: 01-17-2008, 10:44 PM
  5. random numbers
    By carlos123 in forum New To Java
    Replies: 1
    Last Post: 12-22-2007, 02:56 AM

Posting Permissions

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