How to do a random-and-unique generator?

Question

I already wrote a random generator which take arguments a and b, where a is minimun and b is maximum value, like this randomGenerator(int a, int b)

What I want to do next is: Using a loop, then generate 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 the loop, there is a high % that same number will appear more than once. Any idea how to do it?

My own way is:

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

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

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

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

• "shuffle" it

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

In java world, is there a "shuffle" function or I need to create my own?

Answer 1

Take a list with elements sequentially distributed from a to b, shuffle it and return element with subsequent index on each request.

Answer 2

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

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

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

Answer 3

If your idea is to get 8 random numbers you can always use a dictionary/hash or List (which has a 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 aren't at least 8 distinct values between a and b this will get stuck in an infinite loop. I'd put a trap for that before starting.

With just 8 values a simple ArrayList is probably the easiest thing to use. If you had hundreds or thousands of values, running through all of them for each new entry could be prohibitive, and you might want to do something more sophisticated, like use a HashMap, or keep a separate array of flags of what values were used, or some such.

Answer 5

If your range is small (or close to the number of elements you're to select), the solutions proposed above are fine.

If your range gets large, a far more efficient (and clear) way to do it 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'd add one important caveat: don't use a List, use a HashSet. Dusting off my Computer Science nerd terminology, checking whether an element already exists in a List runs in O(n) time; doing the same thing with HashSet gives you O(lg n) performance, which is much faster. For a small data set (like 8 numbers between 1 and 10), it's trivial. For a large data set, it can make a difference.

Something like this ought to do it:

    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 doesn't exceed your range, of course.

If the order is important, you stick them in aList after using the HashSet to confirm it's a new number. Or just dump the HashSet into a new List and shuffle it.

Answer 7

There's a built in shuffle function in the Collections class.

e.g.

List values = new ArrayList();

for( int i = 1; i < 10; i++ ) {
    values.add(i);
}

Collections.shuffle(values);