CODEWITHSUNDEEP
javaarrayssortingfor-loopif-statement
dwin812
dwin812

Reputation: 133

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

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.

Upvotes: 0

Views: 904

Answers (3)

WJS
WJS

Reputation: 40057

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]

Upvotes: 0

Gautham M
Gautham M

Reputation: 4935

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];
}

Upvotes: 4

user14940971
user14940971

Reputation:

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]

Upvotes: 1

Related Questions