How to generate an array of pseudo-random, unique, sorted integers without using an if statement?

Question

I need to create an array of pseudo-random unique integers that are already in an ascending order without using an if statement. For example:

[3,5,7,12]

So far I was able to come up with this code, which repeats some numbers and doesn't put the integers in sorted order.

int[] arr = new int[r.nextInt(10)];
for (int i = 0; i < arr.length; i++) {
    int randInt = r.nextInt(arr.length);
    arr[i] = randInt;
}

What is the best way to work around this? Note: I have to not use the ArrayList and sort method.

You could use a binary tree. Then you have the check if a value already exists and the insertion in sorted order all in a single transaction with *O(log n)* complexity. — akuzminykh, Feb 26 '21 at 06:56
Does this answer your question? [Unique Random Integer Generator](https://stackoverflow.com/questions/16519022/unique-random-integer-generator) or https://stackoverflow.com/questions/20039025/java-array-of-unique-randomly-generated-integers or https://stackoverflow.com/questions/25012033/add-unique-random-numbers-to-an-integer-array. Maybe next time you can search before you ask — Joakim Danielson, Feb 26 '21 at 06:56
`while (condition) { /* code */ break; }` kind of works like an `if` (and good to confuse any reader) — , Feb 26 '21 at 07:11

Gautham M · Accepted Answer · 2021-02-26T10:54:30.983

You could add the previous random number and add to the current random number to ensure that it is greater than the previous one. If you want to have a bound on the random number then you could use nextInt(int bound). I would recommend the use of a bound to avoid any possible overflows.

Random r = new Random();
int prev = r.nextInt(); // seed value may or may not be added to list.
int size = 10; // desired size of random list
int[] rands = new int[size];
int bound = 1000;

for (int i = 0; i < size; i++) {
    // this ensures that new number is always greater than the previous one
    rands[i] = (prev + 1) + r.nextInt(bound);
    prev = rand[i];
}

If all the numbers needs to be in a given range, we need to use arithmetic progression formula. aN = a +(n-1) d. we need to compute the d and add this to the previous random number to ensure the new number is greater.

So in a normal arithmetic progression, starting from a if we keep on adding d, n times, then we would surely reach aN. So to generate a random ascending series such that the last number is less than or equal to aN, we need to add a random number that is less than or equal to d and greater than 0 (to ensure uniqueness of series elements). So we add nextInt(d) + 1 during each iteration.

Random r = new Random();
int aN = 20; // desired max value
int n = 10; // desired size of random list
int[] rands = new int[n];

int seed = r.nextInt(aN / 2); // divide by 2 to ensure it is not close to aN
int d = (aN - seed) / (n - 1);
// This d would be passed to the prev random number to get the new random number.
// This ensures that that last element never crosses the max range even if
// `nextInt` returns the maximum possible value (d-1).

rands[0] = seed;
int prev = seed;
for (int i = 1; i < n; i++) {
    rands[i] = prev + r.nextInt(d) + 1;
    prev = rand[i];
}

wow, this is genius! But can you give me a hint if I want the random numbers in the array to be within some range: for example from 0 to 20? like [1,2,5,12,18, 19] — dwin812, Feb 26 '21 at 08:33
@dwin812 i have added one. But it is not foolproof without using an `if` condition. This is because `nextInt` could return a very small number including a 0. So, to ensure uniqueness we might need to use an `if` — Gautham M, Feb 26 '21 at 08:50
@GauthamM - You do not need `temp`. You can simply write `rands[i] = (prev + 1) + r.nextInt(bound); prev = rands[i];` — Arvind Kumar Avinash, Feb 26 '21 at 09:32
@ArvindKumarAvinash Yes, i just used temp to focus on the operation — Gautham M, Feb 26 '21 at 09:34

score 1 · Answer 2 · 2021-02-26T10:18:21.093

Without ArrayList and sort method: you can use TreeSet, which provides ascending order for integers and guarantees unique values:

TreeSet<Integer> set = new TreeSet<>();
while (set.size() < 10) {
    set.add((int) (1 + Math.random() * 100));
}

int[] arr = set.stream().mapToInt(Integer::intValue).toArray();

System.out.println(Arrays.toString(arr));
// [15, 20, 30, 42, 46, 55, 59, 63, 92, 98]

WJS · Answer 3 · 2021-02-26T13:48:21.690

You could use an instance of Random and stream the values.

Random r = new Random();
int min = 1;
int max = 20_000;
int count = 19_999;
int[] vals =
        r.ints(min, max).distinct().limit(count).sorted().toArray();

The above works fairly fast on my machine but it is not very efficient (especially since in that case you have all the integers from 1 to count in sorted order).

It is imperative that count <= max-min or it will never finish executing since eventually, no subsequent value generated will ever be distinct. And as max-min - count increases, so does the efficiency. It's related to the Pigeonhole Principle.

A more realistic example might be


int[] vals =
        r.ints(1, 100).distinct().limit(10).sorted().toArray();
System.out.println(Arrays.toString(vals));

Prints

[9, 15, 18, 45, 68, 70, 72, 74, 95, 96]

How to generate an array of pseudo-random, unique, sorted integers without using an if statement?

3 Answers3