Random numbers without repeatation

[Kunal Lakhani]

Hello

How to generate numbers without repeating the earlier generated number?

[Jeff Verdegan]

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]

Those aren’t random numbers. That is called “random selection from a declining population” or something similar.

[Rajat Jindal]

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]

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]

What you need to do is figure out a way to check each number generated against the previously generated numbers.

[Jeff Verdegan]

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]

+1

or
++

[fred rosenberger]

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]

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]

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]

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]

How about creating a vector for given range. Generate index using pseudo random generator. And then remove that number.

[Jeff Verdegan]

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]

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]

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]

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]

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]

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]

Thanks a lot Jeff Verdegan, Saurabh Pillai,Campbell Ritchie, fred rosenberger, Vishal Hegde, Vince Stout, Rajat Jindal

[Rajat Jindal]

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

import java.util.Random;

public class RandomSeed {
	public static void main(String[] args) {
		Random rand = new Random();
		rand.setSeed(4455);
		for(int i=0;i<10;i++)
		{
			int x = rand.nextInt(45);
			System.out.println(x);
		}
	}
}

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

import java.util.Random;

public class RandomSeed {
	public static void main(String[] args) {
		Random rand = new Random();

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

		for(int i=0;i<10;i++)
		{
			int x = rand.nextInt(45);
			System.out.println(x);
		}
	}
}

[Campbell Ritchie]

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]

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]

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]

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]

I am confused after setting seed also can we get repeated numbers ??

[Jeff Verdegan]

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]

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]

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]

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]

You’re welcome

[Kunal Lakhani]

This may be the right implementation.

import java.util.*;
import java.util.Random;

public class RandomSeed {
	public static void main(String[] args) {
		Set<Integer> listOfRandom = new HashSet<Integer>();
		Random rand = new Random();
		
		while (listOfRandom.size() != 10) { //generating 10 numbers between 1 to 70
			int x = rand.nextInt(70);
			if ((listOfRandom.contains(x) || listOfRandom.contains(0))) {
			} else {
				listOfRandom.add(x);
			}
		}
		System.out.println(listOfRandom);
		
	}
}

[Martin Vajsar]

We had a pretty detailed discussion of the same topic recently.

[Joanne Neal]

Kunal Lakhani wrote:This may be the right implementation.

import java.util.*;
import java.util.Random;

public class RandomSeed {
	public static void main(String[] args) {
		Set<Integer> listOfRandom = new HashSet<Integer>();
		Random rand = new Random();
		
		while (listOfRandom.size() != 10) { //generating 10 numbers between 1 to 70
			int x = rand.nextInt(70);
			if ((listOfRandom.contains(x) || listOfRandom.contains(0))) {
			} else {
				listOfRandom.add(x);
			}
		}
		System.out.println(listOfRandom);
		
	}
}

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]

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.

while (listOfRandom.size() != 10) { //generating 10 numbers between 1(inclusive) to 70(exclusive)  
            int x = rand.nextInt(70); 

            if (x==0) {
			} else {
				setOfRandom.add(x);
			}

Hope this works better.

[Joanne Neal]

I'd write it as

if (x != 0) {  
    setOfRandom.add(x);  
}  

but apart from that it looks okay.

[Mike Simmons]

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:

int x = rand.nextInt(70) + 1;
setOfRandom.add(x);

or

int x = rand.nextInt(69) + 1;
setOfRandom.add(x);

depending on what the intended range actually is.

[Kunal Lakhani]

Thanks Joanne, Mike