Java how to add a Random Generator that excludes a certain number?

Question

Suppose I wanted to generate random numbers taken from ArrayList:(1,2,3,4,5,6,7,8,9,10)

A Random Generator produces 5.

List gets updated- AL:(1,2,3,4,6,7,8,9,10)

Next Random Number cannot be 5.

I am writing a program that generates random numbers from a arraylist and once it generates the random number the list removes that number and the next random generated digit cannot be that number.

ArrayList<Integer> numsLeft = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));

  Random randomGenerator = new Random();

 int number = 0; 
 String cont;

 do
 {
 number = randomGenerator.nextInt(numsLeft.size()); 
 numsLeft.remove(number);

  System.out.println (number + " continue (y/n)");
  cont = (stdin.readLine());
 } 
 while (cont.equalsIgnoreCase("y"));

But the only thing I can do here is lower the size...

http://docs.oracle.com/javase/7/docs/api/java/util/Random.html

http://stackoverflow.com/questions/158716/how-do-you-efficiently-generate-a-list-of-k-non-repeating-integers-between-0-and — Anupam Saini, Nov 11 '13 at 16:05

score 6 · Accepted Answer · answered Nov 11 '13 at 15:45

The easier approach is to simply shuffle your list then use the numbers in the shuffled order:

List<Integer> nums = new ArrayList<Integer>();
for (int i = 1; i < 11; i++)
    nums.add(i);
Collections.shuffle(nums);

Now they are in random order, just use them one by one:

for (Integer i : nums) {
    // use i
}

score 0 · Answer 2 · answered Nov 11 '13 at 15:41

You could make an array of the available numbers. Then, the random number generator gives you the position in that array for the number that you want. Probably a linked list or something would be more efficient, but the concept is the same. So, with your example, you'd pull 5 the first time. The second time, you'd have this in your list: 1, 2, 3, 4, 6, 7, 8, 9 If your random number was 5 again, the fifth position is 6. Pop the six out, shift 7, 8, 9 over one, and decrement your random number generator to be 1-8 instead of 1-9. continue on.

of course, looking at your code, it looks like that is what you are trying to do already.

What seems to be the issue with your code? What results are you getting?

score 0 · Answer 3 · answered Nov 11 '13 at 15:41

number = randomGenerator.nextInt(numsLeft.size()); 
numsLeft.remove(number);

You are now printing the random index that you are generating, not the number that was removed from the list. Is that what you wanted? I think you really meant this:

int index = randomGenerator.nextInt(numsLeft.size());
number = numsLeft.remove(index);

You could also do this using by randomly shuffling the list and then just going through it:

List<Integer> numsLeft = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));

// Shuffle the list randomly
Collections.shuffle(numsLeft);

do {
    // Remove the first number each time
    int number = numsLeft.remove(0);

    System.out.println (number + " continue (y/n)");
    cont = (stdin.readLine());
} while (cont.equalsIgnoreCase("y"));

score 0 · Answer 4 · answered Nov 11 '13 at 16:06

Why don't you create a hash map to take care of this. So your hash map can contain something like

Map[(1,1), (2,2), (3,3), ...] or Map[(1,true), (2,true), (3,true), ...]

So if you generate a number, then you can do something like:

String value = map.get(key); or boolean present = map.get(key); 

if(value != null) or if(value == present)

map.remove(key), or you can even update the data and instead of removing the key you can update it and add the word removed or a boolean as previously suggested. But this way you can keep track of all the entries and removals in your map for each of the key values which would be your list of numbers.

score 0 · Answer 5 · answered Nov 16 '13 at 00:05

remove can be pretty expensive operation when list is long. Shuffle is too - especially if you only need a few numbers. Here is another algorithm (it is famous but I can't find the source right now).

put your N (ordered) numbers in a list
Choose a random number m between 0 and N-1
Pick the element at location m. This is your unique random number
SWAP element m with the LAST element in the array
Decrement N by 1
Go to step 2

You "set aside" the numbers you have used in step 4 - but

Unlike shuffle, your initialization is fast
Unlike remove, your remove operation only takes moving one element (instead of, on average, N/2)
Unlike the "pick one and reject if you saw it before", your efficiency of picking a "new" number doesn't decrease as the number of elements picked increases.

Java how to add a Random Generator that excludes a certain number?

5 Answers5