How to make a random and unique generator?

Question

I already wrote a random generator that takes a and b arguments, where a is the minimum and b is the maximum value, like this randomGenerator (int a, int b)

Next I want to: use a loop, and then generate a unique number from a to b. Example:

I want to have 8 unique numbers, int a = 1; int b = 10; int value; 

If I do a loop, there is a high% that the same number will appear more than once. Any idea how to do this?

My own way:

 while(int i <= 8){ randomGenerator(a,b); // if value is not in array, then insert into array } 

I am stuck in the comment part. Is there a way to check if a variable exists in an array?

Edit, based on nailxx's answer, I understand:

• take a list from a to b (if you follow my example, 1-10)

• "shuffle" it

• take the first 8 items. Is that what you mean?

Is there a "shuffle" function in the java world or do I need to create my own?

Answer 1

Take a list with items sequentially distributed from a to b , shuffle it, and return the item followed by an index for each query.

Answer 2

Since the size of your sample is almost the same as the size of your rage, you can simply generate all integers from 1 to 10, shuffle them , then take the first 8 elements.

If the sample size (k) is much smaller than the size of the range (n), you can use the Fisher-Yates shuffle variation, where you stop the algorithm after k steps instead of shuffling the entire array.

If the sample size is small, but the size of the range [0, n) is too large to be stored in memory, you can use another variation in which you first select the random number s1 in [0, n). Then you select a number in [0, n-1) and add it to it if it is equal to or greater than s1, giving s2. Then select the number in [0, n-2) and add to it for each of s1, s2 a value greater than or equal, etc.

Answer 3

If your idea is to get 8 random numbers, you can always use a dictionary / hash or List (which has the Contains (int i) method), and then convert the dictionary or list to an array:

 List<int> x = ...; int[] data = x.ToArray(); 

Answer 4

 List<Integer> list=new ArrayList<Integer>(8); while(int i <= 8){ do { Integer n=randomGenerator(a,b); } while (list.contains(n)) list.add(n); } 

Of course, if there are at least 8 different values ​​between a and b, this will get stuck in an infinite loop. I would set a trap for this before starting.

With just 8 values, a simple ArrayList is probably the easiest way to use. If you have hundreds or thousands of values, you can use them for each new record, and you can do something more complicated, for example, use the HashMap or save a separate array of flags, which values ​​were used, or some of them.

Answer 5

If your range is small (or close to the number of items you should select), the solutions above are in order.

If your range becomes larger, a much more efficient (and clear) way to do this is as follows:

 int[] pickRandom(int numberOfChoices, int lowerBound, int upperBound) { Set<Integer> choices = new HashSet<Integer>(); while (choices.size() <= numberOfChoices) { choices.add(yourRandomGenerator (lowerBound, upperBound)); } int[] ret = new int[choices.size()]; int ii=0; for (Integer choice: choices) { ret[ii++] = choice.intValue(); } return ret; } 

Answer 6

There are some good answers here, but I will add one important caveat: do not use List , use HashSet . Elimination of my terminology "Computer Science", checking whether an element exists in the list, is performed in O (n) time; doing the same with a HashSet gives you O (lg n) performance, which is much faster. For a small data set (for example, 8 numbers from 1 to 10) this is trivial. For a large dataset, this can make a difference.

Something like this should do this:

 HashSet resultSet = new HashSet(); while (resultSet.size() < targetSize) { resultSet.add(randomGenerator(a,b)); } 

... with a sanity check in your preconditions to make sure your target size does not exceed your range, of course.

If order is important, you put it in a List after using a HashSet to confirm it with a new number. Or just drop the HashSet into a new List and shuffle it.

Answer 7

The Collections class has a built-in shuffle function.

eg.

 List values = new ArrayList(); for( int i = 1; i < 10; i++ ) { values.add(i); } Collections.shuffle(values);
List values = new ArrayList(); for( int i = 1; i < 10; i++ ) { values.add(i); } Collections.shuffle(values);