Generating many random numbers within a range with some exceptions in java

Question

I need to generate lots of random numbers within a range with some exceptions. Right now I'm planning to do it in this way,

public class Main
{
 static List<Integer> except = Arrays.asList(5, 6, 11, 12, 17, 18, 23, 25, 28, 29);
 
 
 public static void main(String[] args) {
 
 List<Integer> randomNums = new ArrayList<>();
 
 Random random = new Random();
 
 int z;
 for(i=0; i<20; i++) {
 z = random.nextInt(30);
 while(except.contains(z)) z = random.nextInt(30);
 randomNums.add(z);
 } 
 
 System.out.println(randomNums);
 }
}

In my case the size of "except" and "randomNums" will be much higher. So the code will spend much time in the while to avoid numbers that I don't want.

I'm curious to know can I speed up my code? If I can remove the while loop then definitely it will be an O(n). But how can I do that. Thanks.

• vanje: Use a Set instead of a list for except. Then the contains() method has O(1) instead of O(n).
• K. Martin: It's not possible to remove the while loop as far as I can tell!
• abhimanyue: I'm thinking, if I can use some sort of mapping from "random number" --> "numbers I need (excluding numbers from except)" then I can remove the while loop. @K. Smith
• Sebphil: is the range of your random numbers changing or constant?
• K. Martin: You could create a list of acceptable numbers and then use a random generator to take numbers from given positions in this list, however I don't know how useful this is as you will have to generate this list at the beginning.

Answer 1

My suggestion is you make a list of all the numbers you do want in your result and each time pick a random member from that list. It requires some initialization, but your loop should run fast after that.

 int maxExclusive = 30;
 Integer[] baseArr = new Integer[maxExclusive];
 Arrays.setAll(baseArr, Integer::valueOf);
 List<Integer> base = new ArrayList<>(Arrays.asList(baseArr));
 base.removeAll(except);
 
 List<Integer> randomNums = new ArrayList<>();
 
 Random random = new Random();
 
 for (int i = 0; i < 20; i++) {
 Integer z = base.get(random.nextInt(base.size()));
 randomNums.add(z);
 }
 
 System.out.println(randomNums);

Example output:

[1, 10, 27, 2, 24, 22, 7, 8, 0, 27, 19, 27, 15, 14, 21, 22, 13, 24, 2, 13]

• WJS: @abhimanyue As an aside, just in case you don't want duplicates of the specialize list, you can use Collections.shuffle and pull them out of the list in sequence.

Answer 2

Here is one approach:

 public static void main(String[] args) {
 final int exceptMin = 5;
 final int exceptMax = 29;
 Set<Integer> except = new HashSet<>(
 Arrays.asList(5, 6, 11, 12, 17, 18, 23, 25, 28, 29)
 );
 List<Integer> safeValues = getSafeValues(except, exceptMin, exceptMax);
 List<Integer> randomValues = getRandomValues(except, safeValues);
 }
 public static List<Integer> getSafeValues(Set<Integer> except, int exceptMin, int exceptMax) {
 List<Integer> safeValues = new ArrayList<>();
 for(int i = exceptMin; i < exceptMax; i++) {
 if(!except.contains(i))
 safeValues.add(i);
 }
 return safeValues;
 }
 public static List<Integer> getRandomValues(Set<Integer> except, List<Integer> safeValues) {
 List<Integer> randomValues = new ArrayList<>();
 for(int i = 0; i < 800_0000; i++) {
 int randomNumber = getRandomValue(except, safeValues);
 randomValues.add(randomNumber);
 }
 return randomValues;
 }
 public static int getRandomValue(Set<Integer> except, List<Integer> safeValues) {
 ThreadLocalRandom random = ThreadLocalRandom.current();
 int randomNumber = random.nextInt(0, 30);
 if(except.contains(randomNumber)) {
 int randomIndex = random.nextInt(safeValues.size());
 randomNumber = safeValues.get(randomIndex);
 }
 return randomNumber;
 }

So just use another list that stores values that are safe to use and pick one of these if the randomly generated one failed. And as already mentioned by @vanje it uses a HashSet to perform your lookups because it has a constant time complexity for that (https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html).

This approach performs (on my machine) as follows:

generated Numbers time in ms
800_000 300
400_000 156
200_000 87
100_000 38

I used the exceptions specified in your answer and generated numbers between 0 (inclusive) and 30(exclusive) so there are a lot of "misses".

However, this approach will cost more memory than generating "fresh" random values and needs some preparation. For example when the exceptions are {0, 100_0000} you will generate a lot of "safe" numbers. You could split the safeNumbers list into multiple lists to deal with that. Besides that this method might screw up the distribution of your random numbers (if that is a problem for you).

Edit: As I wrote this answer I did not realize that @Ole V.V. also used this approach. I will delete this answer if requested.

• Anonymous: I suggest that you can leave the answer here. For one thing, some might find your time measurements interesting. Also the use of the HashSet may be considered an improvement over my code.

Answer 3

Java simple way to get List of Random Integers in:

RandomGenerator random = RandomGenerator.getDefault();
random.nextInt(1, 100);
List<Integer> list = random.ints(1, 100)
 .limit(100)
 .boxed()
 .toList();
list.forEach(System.out::println);