• Post Reply Bookmark Topic Watch Topic
  • New Topic

How to write a Random Number Generator that will not contain any repeat value in a range?  RSS feed

 
Ranch Hand
Posts: 674
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi there

I am trying to write a Random Number Generator that will not contain any repeat value in a given range

something this I have try so far



although this code generate random numbers but some values are also getting duplicate.So how to write a program for random number that will not repeat any integer in range?

Thank
 
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you have this requirement that means you can only generate as many "random" numbers as there numbers in the given range. What do you plan to do when you run out of unique numbers?
 
Kishor Joshi
Ranch Hand
Posts: 674
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to design some test cases of a problem range is 1 to 1000000 or can be more and I need all of them to be unique and some task then on these numbers
 
Ranch Hand
Posts: 934
4
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can't guide Random generator to generate always unique numbers. But you can maintain them in a Set which stores unique number
only. So you can check if that number already present or not, if yes then generate again.

But then you need to have long range also performance may be compromise for fair large numbers.
 
Bartender
Posts: 1840
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another option if the range isn't too large is to generate all of the potential numbers sequentially into an array, and then 'shuffle' it.
That way you can guarantee the uniqueness.
Not necessarily the most space efficient, but if it suits...
 
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Depends on the size of the range. It is not possible correctly to shuffle a range if the number of combinations is larger than the range of “random” numbers available. There was a discussion recently where the impossibility of shuffling 52 cards properly is mentioned. How much worse for 10000000 numbers; that would require log₂(1000000!) bits, which evaluates exactly to a lot. So you would have to spend a very long time shuffling the List repeatedly to get it anything like random. You can try looking for a “random” index in a List and remove the number found each time, or you can try adding to a set as previously suggested. All options will have performance problems.
  • Shuffling: hours shuffling repeatedly then rapid performance after shuffling completed.
  • Removal from List: Gradually gets faster as List is exhausted.
  • Checking for duplicates in Set: gradually gets slower as collisions increase.
  • I think I would try removal from a List myself.

    That is not called random numbers, but random selection from a decreasing population (or something similar).
     
    Tushar Goel
    Ranch Hand
    Posts: 934
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    then why not use map. Its gives o(1) operation. fast enough.
     
    Campbell Ritchie
    Marshal
    Posts: 56600
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Please explain how you would use a Map to ensure uniqueness and how it would maintain fast execution.
     
    Tushar Goel
    Ranch Hand
    Posts: 934
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I first initialized map with all the values required. Say, 1 to 100000. All these integers i will
    treat it as unique key. Value can be anything. I choose to 0 or null. Then i can remove
    key from it one by one or randomly(depend upon the random generator values or something else)
     
    Bartender
    Posts: 689
    17
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That solution looks to be the same as using a Set to me.
     
    Tushar Goel
    Ranch Hand
    Posts: 934
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I think user also wanted to remove the number once used. So, in map i suppose removing is easy then
    list.
     
    Mike. J. Thompson
    Bartender
    Posts: 689
    17
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    But a Set is not a List. Removal from a Set has similar properties to removal from a Map. A HasMap is actually backed by a HashSet I believe.
     
    Tushar Goel
    Ranch Hand
    Posts: 934
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    yeah for set and map makes same thing. Set is using internally map.
     
    Campbell Ritchie
    Marshal
    Posts: 56600
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I still think the use of a Map will cause collision problems later on. You can either add things to a set and risk collisions or you can remove pairs from a map and risk empty values later on. As MJT says, is there actually a difference between the two approaches?
     
    Tushar Goel
    Ranch Hand
    Posts: 934
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I dont think any difference between set and map. I was telling to use map with respect to list.
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!