Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Random numbers without repeatation  RSS feed

 
Kunal Lakhani
Ranch Hand
Posts: 622
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello

How to generate numbers without repeating the earlier generated number?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kunal Lakhani wrote:Hello

How to generate numbers without repeating the earlier generated number?


What do you think? you should start by thinking about how you might do it "by hand" (that is, without using Java), maybe doing a web search, and then, if you get stuck, post what you've got so far and describe clearly exaclty what part is giving you trouble.
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Those aren’t random numbers. That is called “random selection from a declining population” or something similar.
 
Rajat Jindal
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Its very easy.. you just need to set the seed for the java.util.Random class.. check the API and you will get the solution...
I am not telling you so that you can improve your search capabilities.. In case still you face any problem.. write back, I will give you a solution.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rajat Jindal wrote:Its very easy.. you just need to set the seed for the java.util.Random class..


No, he doesn't need to do that, and even if he chooses to do it, there's still more that he needs to do beyond that.

In case still you face any problem.. write back, I will give you a solution.


No, please DontBeACodeMill.(⇐click) It's better to LetThemDoTheirOwnHomework.(⇐click)
 
Vince Stout
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What you need to do is figure out a way to check each number generated against the previously generated numbers.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vince Stout wrote:What you need to do is figure out a way to check each number generated against the previously generated numbers.


That's one approach. Depending on how many numbers he needs to generate and what the range is to choose from, it may or may not be the best approach.
 
Vishal Hegde
Ranch Hand
Posts: 1078
Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
+1

or
++
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vince Stout wrote:What you need to do is figure out a way to check each number generated against the previously generated numbers.

The problem there is that as you select more and more numbers, it takes longer and longer to find a 'valid' one.

this may not be a problem if the domain is small or you only need relative a few outputs...but if the domain is large (say, millions) and you need to eventually output them all...it can take a long time to get that 999,990th value, because you keep picking ones you've already used.
 
Kunal Lakhani
Ranch Hand
Posts: 622
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I did it using array, where i check each number generated against the previously generated numbers. This will not be efficient when having large volume of data

So, which approach should i go for?
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suggest you use a Set<Integer> or similar. Check whether your number is already an element of the Set. The contains method runs in constant time (if you find the right implementation), which is faster than iterating an array (linear time).
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kunal Lakhani wrote:I did it using array, where i check each number generated against the previously generated numbers. This will not be efficient when having large volume of data

So, which approach should i go for?

You have not given us NEARLY enough information to answer that. What will be your Domain? How many possible values are there? How many values do you need to pick? Do you have a defined speed requirement, or is it just some vague "I don't want it to take too long" statement? What are your memory restrictions?

Writing software usually requires one to balance about 73 different competing requirements. You can improve 'A' and 'B', but at the cost of 'C' and 'D'. Unless you give us an idea what your requirements are, and what has the most priority, there isn't much concrete advice we can really give you.
 
Saurabh Pillai
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about creating a vector for given range. Generate index using pseudo random generator. And then remove that number.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Saurabh Pillai wrote:How about creating a vector for given range. Generate index using pseudo random generator. And then remove that number.


I wouldn't use Vector, but, yes, that's one possible approach. Again, though, since he hasn't told us any of the details of his requirements, there's no way to know if that approach will be viable.
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Saurabh Pillai wrote:How about creating a vector for given range. . . .
Vector? What’s wrong with ArrayList? Why is legacy code like Vector and StringTokenizer suggested so frequently?

As Fred has suggested, the solution depends on many factors. Do you want a few numbers out of a large range, or most of the numbers from a small range. That will determine whether using a set or a list would be more efficient.
 
Kunal Lakhani
Ranch Hand
Posts: 622
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I dont have much requirements. Just have to fetch max 70 random numbers, out of 200-300. And there is no such speed requirements.
 
Saurabh Pillai
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Saurabh Pillai wrote:How about creating a vector for given range. . . .
Vector? What’s wrong with ArrayList? Why is legacy code like Vector and StringTokenizer suggested so frequently?

The only reason I suggested Vector because it can change in size(grow/shrink) after creation (while array can't). But yes, ArrayList is better choice here.

I think the main benefit of my approach is to avoid the search for duplication.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kunal Lakhani wrote:Just have to fetch max 70 random numbers, out of 200-300. And there is no such speed requirements.


Both of those sentences are in contradiction to what you said earlier:
Kunal Lakhani wrote:
This will not be efficient when having large volume of data


So which is it?

Are you concerned about "efficiency with a large volume of data"? If so, you must be able to specify how efficient it needs to be, with actual numbers, and how much data you need to process, with actual numbers.

Or do you just need 70 numbers in the range of 200-300, as stated here? If so, then Campbell's suggestion of a Set<Integer> will work fine for you. Generating all the numbers in the range, shuffling them, and pulling off the first 70 will also work fine. Pick whichever approach you like best.

 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Saurabh Pillai wrote:
I think the main benefit of my approach is to avoid the search for duplication.


Yes, that works for small enough ranges, which the OP has finally said he has. If he had to choose from 0..Integer.MAX_VALUE, this would not be a good approach.
 
Kunal Lakhani
Ranch Hand
Posts: 622
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks a lot Jeff Verdegan, Saurabh Pillai,Campbell Ritchie, fred rosenberger, Vishal Hegde, Vince Stout, Rajat Jindal

 
Rajat Jindal
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I dont want to be a code-mill but this I think I should post the solution for the problem.. I know it has problem that it will always generate the same sequence of Random numbers but I will provide a solution for that also



in case you set the seed value as 4455 as shown in above code, it will always generate the same sequence of numbers whenever you run the program. For that, better solution is to set the seed value with some random number every time you run the program



rand.setSeed(rand.nextInt(1000000));


 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rajat Jindal wrote:. . . but this I think I should post the solution for the problem.. . . .
Not at all. If we think you ought not to post a solution, we shall delete it. But your suggestion will not fulfil the original poster’s request.

. . . and both 70 and 200-300 count as small amounts.
 
Rajat Jindal
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok.. I will not post the solution but the way discussion was going on ...was not going to provide a optimum solution...
In my code.. we can easily modify it towards the requirements if we provide next int value to 100 and add the range values to it so that it always lies in between those values
I hope then it will work.. make minor changes to code and you will achieve n number of solutions to the m no of problems
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No, it won’t work. Not at all. You cannot guarantee non-repetition. It is an attribute of randomness that repetition is permitted. You can prevent repetition by using a declining population, which you can achieve with a set or the two techniques using lists. There are at least two different ways to use a set, too.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rajat Jindal wrote:Ok.. I will not post the solution but the way discussion was going on ...was not going to provide a optimum solution...


He was suggested two approaches that would both work very well for his requirements.

And note that the goal of this site is not to provide solutions. It is to give people the tools they need to find their own solutions.
 
Rajat Jindal
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am confused after setting seed also can we get repeated numbers ??
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rajat Jindal wrote:what do you suggest ??


Campbell already suggested an easy and appropriate appoach:
Campbell Ritchie wrote:I suggest you use a Set<Integer> or similar. Check whether your number is already an element of the Set.


Or I guess in my code setSeed() itself is not required.


Don't use the seed unless you want to repeat the same sequence (which is sometimes desirable in certain simulations).
 
Rajat Jindal
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I guess by using setSeed() method we cant remove repeated values and ultimate option is to use some kind of solution like Set<Integer>.
Can anyone confirms me whether setSeed() remove repetition of numbers or not?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rajat Jindal wrote:I guess by using setSeed() method we cant remove repeated values and ultimate option is to use some kind of solution like Set<Integer>.
Can anyone confirms me whether setSeed() remove repetition of numbers or not?


Calling setSeed() does NOT prevent repetition. I don't know why you thought it would. It guarantees that you will get the same sequence of numbers the next time you call setSeed() with the same value.
 
Rajat Jindal
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yes, Initially I thought it would not allow repeated value ( I made wrong assumption, don't know why I made this assumption ) but Campbell Ritchie made me to think on my wrong assumption lines and Jeff you confirmed it.
So special thanks to both of you Jeff Verdegan and Campbell Ritchie .

 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You’re welcome
 
Kunal Lakhani
Ranch Hand
Posts: 622
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This may be the right implementation.

 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
We had a pretty detailed discussion of the same topic recently.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kunal Lakhani wrote:This may be the right implementation.


If you're going to use a Set don't use a variable name that suggests it is a List.
A Set cannot contain duplicates so there is no need to check if the value is already in the Set.
Is 70 a valid value ? If so, your rand.nextInt call is wrong.
You also have a logic error - once you add the value zero to your Set you will never add any more numbers because your if condition will always be true.
 
Kunal Lakhani
Ranch Hand
Posts: 622
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Joanne Neal.

You also have a logic error - once you add the value zero to your Set you will never add any more numbers because your if condition will always be true.




Hope this works better.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd write it as

but apart from that it looks okay.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, there is still the matter of whether 70 is a valid value or not. Evidently 0 is not valid, but there's an easier way to do that. I suggest reading carefully what random.nextInt() returns, exactly. Then try one of the following:


or

depending on what the intended range actually is.
 
Kunal Lakhani
Ranch Hand
Posts: 622
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Joanne, Mike
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!