Generating unique random numbers

Question

How can I generate 9 random numbers between 1 to 9,without repetition, one after another. Its like: Lets assume that the first random number generated is 4, then the next random number has to be in [1, 9] - {4}. My first approach was to add each randomly generated number to a set, and so avoid duplication. But then in worse cases, like we have already generated 6 and we have to generate 3 more numbers, the process goes a little slow. And when the range is changed from [1, 9] to [1, 1000], this approach doesn't sound correct. Can anyone suggest an alternative approach.

Answer 1

Start with a sorted array (trivialy easy to create by a for-loop); then shuffle bey swapping each array element with another (random chosen) element. To avoid the bias discussed in the comments, the index of the other element must be equal or higher than the index of the first element. If the indexes are equal, then the element is not swapped. (The original version of this answer contained a sentence about the possibility of the element being swapped back, but this is now obsolete since this can't happen anymore with the highlighted modification)

Answer 2

If you are not interested in implementing yourself an algorithm to do what you want, you can use a simply way, already implemented in the Java libraries.

You can create a collection (a sorted List) of Integer (start to end, where start=1 and end=9 in your example), and then use the method Collections.shuffle(list);, for instance in this way:

static List<Integer> randArray(int start, int end) { //specify start/end
    List<Integer> randList=new ArrayList<>(end-start+1); //create list
    for (int k=start;k<=end;k++) { //generate integers in order
        randList.add(k); //add integers to the list
    }        
    Collections.shuffle(randList); //reoder randomly the list
    return randList; //return the list with items in random order
}

The shuffle method simply randomly reorder the items of the list.

Answer 3

Following are two possible approaches :-

Method 1 :-

1. Have all numbers in an array with size n.
2. select a number an index at random i = rand(0,size)
3. print arr[i]
4. swap arr[i] and arr[size-1]
5. size = size -1
6. repeat 1 to 5 till list is exhausted.

Time Complexity: O(N)

Space Complexity: O(N)

Method 2:-

1. Select a pool size of K.
2. generate K random integers.
3. show them as first k results.
4. Add them to a hashset.
5. Add all ak+1 for all previous integers in a pool.
6. Add 1 if it is not in hashset.
7. pick a integer r at random from pool and show it .
8. Add r+1 into pool if its not in hashset
9. Do 7 to 8 till pool is exhausted.

Time complexity: O(N)

Space complexity: O(K)

Pro & Cons :-

Method 1: Use this method for small integer ranges as it requires larger space but it is very fast and random.

Method 2: Use this method for larger ranges as it takes memory O(K) which is of your choice. The higher the k the higher is the randomness in the numbers generated. So you can achieve a nice trade off between space and randomness with maintaining good speed.

Answer 4

Create an ArrayList like that:

index 0->index 1->index 2...

[1] -> [2] -> [3]....

Generate a random index value betwen 0 and list.size() and get the position in list:

yourNumberResult = get(randomIndexValue).

Then remove the position in the list:

list.remove(randomIndexValue)

Then repeat this in iteration until list.size()==0

Answer 5

Generate an array for numbers 1 to 9 in sorted order.

int arr[]=new int[9];
for(int i=0;i<9;i++)
   arr[i]=i+1;

Now shuffle the given array.

How to Shuffle an array?

To shuffle an array a of n elements (indices 0..n-1):
   for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i]

References

http://www.geeksforgeeks.org/shuffle-a-given-array/

Answer 6

Using Java 8, the method of Enne could be written like this:

private static List<Integer> generateRandom( int low, int high )
{
    List<Integer> range = IntStream.range( low, high ).boxed()
                                   .collect( Collectors.toList() );

    Collections.shuffle( range );
    return range;
}

Answer 7

public ArrayList<Integer> getRandom(int numbers,int min_value, int max_value)
{     
    HashSet<Integer> list = new HashSet<>();
    Random r = new Random();
    while (list.size()<numbers) {
        list.add(r.nextInt(max_value - min_value) + min_value);
    }
    return new ArrayList<>(list);
}

Alternative:

public ArrayList<Integer> getRandom(int numbers,int min_value, int max_value)
{     
    Random r = new Random();
    ArrayList<Integer> list = new ArrayList<>();
    for(int i=min_value; i<=max_value;i++)
        list.add(i);
    while (list.size()>numbers) {
       list.remove(r.nextInt(list.size()));
    }
    Collections.shuffle(list);
    return list;
}

Alternative:

   public ArrayList<Integer> getRandom(int numbers, int min_value, int max_value) {
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = min_value; i <= max_value; i++) {
        list.add(i);
    }
    Collections.shuffle(list);
    return new ArrayList<>(list.subList(0, numbers));
}