Can you pick N random individual ints in java?

Question

I'm currently looking for a better way, so choose x unique ints from the range of n int. This would be like doing Random.nextInt(range) several times, except that it should never select the same int twice. If this happens, then x > n then the result will contain only n ints

I tried to do it myself, and currently I have done it based on Shuffle Fisher / Yates:

 private static final Random R = new Random(); public static int[] distinctRandoms(int nb, int max) { int[] all = new int[max]; for (int i = 0; i < all.length; i++) { all[i] = i; } if (max <= nb) { return all; } int index; int[] result = new int[nb]; for (int j = 0, k = all.length - 1; k > 0 && j < nb; k--, j++) { index = R.nextInt(k + 1); result[j] = all[index]; // save element all[index] = all[k]; // overwrite chosen with last element } return result; } 

This works, and the performance seems good, but I can't help but think that there still needs to be an even more efficient way to do this, and that I am inventing the wheel. I was thinking of doing something differently if nb > (max / 2) (delete elements, not select elements), but since you cannot trim the array in java, you still copy all the elements you need . This method is expensive if nb = max-1

Is there a built-in way to randomly select individual ints in java?

Change 1:

What I mean is time-efficient. I want it to be fast. I will mainly work with small sets of random ones.

Edit 2:

I tried using shuffle, but it is much more expensive in terms of time due to the creation of the entire additional object.

 public static Integer[] distinctRandoms2(int nb, int max) { ArrayList<Integer> all = new ArrayList<Integer>(max); for (int i = 0; i < max; i++) { all.add(i); } if (max <= nb) { return all.toArray(new Integer[max]); } Collections.shuffle(all); return all.subList(0, nb).toArray(new Integer[nb]); } 

Answer 1

You can use the shuffle method from the java.util.Collections class.

Just create a list of integers from 0 to x-1 , then call the shuffle method on it and take the first nb elements.

Using the shuffle method makes sense when nb is close to max . Therefore, it would be useful for the following pairs of parameters:

• nb=70, max=100
• nb=900, max=1000
• nb=9000, max=10000

but it is not so good for:

• nb=10, max=10^8
• nb=100, max=10^9

It would be nice to combine the above method (using shuffle ) with the Floyd algorithm from another answer. The choice of algorithm should be based on the ratio nb/max . The border coefficient should be selected carefully.

Answer 2

You can use the Floyd algorithm. This is much more efficient than shuffling if the number of items to select is less than their range.

 private static final Random random = new Random(); /** * Converts a set of Integer to an array of int. */ private static int[] setToArray(Set<Integer> aSet) { int[] result = new int[aSet.size()]; int index = 0; for (int number : aSet) { result[index] = number; index++; } return result; } /** * Generates an array of min(count, maxValue) distinct random ints * from [0, maxValue - 1] range. * @param count The number of elements to be generated. * @param maxValue The upper bound of the range(exclusively). */ public static int[] getDistinctRandomNumbers(int count, int maxValue) { Set<Integer> was = new HashSet<>(); for (int i = Math.max(0, maxValue - count); i < maxValue; i++) { int curr = i == 0 ? 0 : random.nextInt(i); if (was.contains(curr)) curr = i; was.add(curr); } return setToArray(was); } 

It has O(count) complexity of time and space, where count is the number of different integers that need to be generated.

Answer 3

It depends on what you mean by Performant and Random .

If you really need something that costs O(1) or similar, you can use the Linear Feedback Shift Register or LFSR . It generates a random sequence of numbers (i.e., statistically random, but theoretically predictable) using a simple XOR operation on the previous number and, therefore, possibly the fastest mechanism.

This approach is most suitable if you want to get an n-bit number. Limiting the range of numbers by dropping those outside the required range can reduce performance.

Answer 4

If by “small sets of randoms” you mean max small, the Collections#shuffle approach is probably as good as you can get.

If max can be arbitrarily large, but nb is small, then using a HashSet may be your best option, although you will have some boxing / unboxign cost. If you want to avoid this cost, you can try using a IntHashSet or a similar primitive HashSet specialization.