This chapter first explains several ways to generate Java random numbers, and then demonstrates them through examples.
Overview:
Will you say here, what's the difficulty of generating random numbers? Isn’t it just to use Java encapsulated random? Of course, it is OK in general, and the algorithms to be explained in this article are also based on this random library function.
This article mainly focuses on the behavior of sampling, and the sampling itself has an implicit rule that is not to have duplicate data. OK, with these instructions. You can first try to use some of your own ideas to generate random numbers without repeated generation.
Algorithm attempts:
Some good algorithms appear, often accompanied by some not-so-good algorithms. However, for algorithms that are not very effective, they generally have one common feature, which is easy to understand and implement. The following is a brief explanation through a step-by-step approach.
First try: Naive random algorithm
This algorithm is easy to understand, it is random! Each time a random number is generated and added to the set.
private void simpleRandom(int start, int end, int count) { System.out.println("Natural Random Algorithm:"); StringBuffer buffer = new StringBuffer(); for (int i = 0; i < count; i++) { int random = NumberUtils.randomInteger(start, end); buffer.append(i == 0 ? ("[" + random) : (", " + random)); } buffer.append("]"); System.out.println(buffer); } The second attempt: Check for existential random algorithm
We know that there is a problem with the above method, that is, there may be duplicate data. So, we thought of checking whether the number already exists when generating a random number, and if it exists, it will be regenerated.
private void checkRandom(int start, int end, int count) { System.out.println("Check existential random algorithm: "); StringBuffer buffer = new StringBuffer(); List<Integer> save = new ArrayList<>(); for (int i = 0; i < count; i++) { int random = NumberUtils.randomInteger(start, end); if (exits(save, random)) { i--; continue; } save.add(random); buffer.append(i == 0 ? ("[" + random) : (", " + random)); } buffer.append("]"); System.out.println(buffer); } The third attempt: Element removal random algorithm
The above algorithm has solved the problem of data duplication. However, one very bad problem is that it may take us a long time to generate sample random numbers (this depends on the face...).
However, here we have new ideas. That is to randomly use a number in a set, and remove it when this is selected. Then, will you not randomly reach this number again when it is random? This solves the problem of repetition of random numbers very well. The code is as follows:
private void removeRandom(int start, int end, int count) { System.out.println("Element removal random algorithm: "); StringBuffer buffer = new StringBuffer(); List<Integer> numbers = initList(start, end); for (int i = 0; i < count; i++) { int random = NumberUtils.randomInteger(count - i); buffer.append(i == 0 ? ("[" + numbers.get(random)) : (", " + numbers.get(random))); numbers.remove(random); } buffer.append("]"); System.out.println(buffer); } Fourth attempt: State transfer random algorithm
In many of my previous blogs, some are state transfer processes in algorithms. State transfer is also one of my favorite algorithms. Figure-1 below marks the value range of random numbers, and the orange number in the sequence is the random sequence in the result. There are some dotted arrows in the bottom sequence, representing the transition of state.
Figure-1 Sampling random number generation algorithm based on state transition
Implementation code:
private void statusRandom(int start, int end, int count) { System.out.println("Status transfer random algorithm:"); StringBuffer buffer = new StringBuffer(); int[] status = new int[end + 1]; for (int i = 0; i < count; i++) { int random = NumberUtils.randomInteger(start, end); System.err.println(random); if (status[random] == 0) { buffer.append(i == 0 ? ("[" + random) : (", " + random)); status[random] = random == end ? start : (random + 1); // It is impossible to have a number before start} else { // Status transfer int index = random; do { index = status[index]; } while (status[index] != 0); buffer.append(i == 0 ? ("[" + index) : (", " + index)); status[index] = index == end ? start : (index + 1); // It is impossible to have a number before start} } buffer.append("]"); System.out.println(buffer); } The fifth attempt: Recursive Floyd random algorithm
The Floyd algorithm is ultimately a state transfer process. The algorithm will require a List or array to store the determined random number. As the name suggests, I will use recursive solutions here. In the process of recursion, we transfer the state of the i-th random number to the i-1 random number. The code is as follows:
private List<Integer> simpleFloyd(List<Integer> list, int count, int start, int end) { if (count == 0) { return list; } list = simpleFloyd(list, count - 1, start, end - 1); int random = NumberUtils.randomInteger(start, end); if (list.contains(random)) { list.add(end); } else { list.add(random); } return list; } Sixth attempt: Iterate over Floyd random algorithm
The idea is similar to the recursive Floyd random algorithm above, but here we add a variable to optimize. There is no need to recurse anymore. The code is as follows:
private List<Integer> iterationFloyd(int start, int end, int count) { System.out.println("Iterative Floyd random algorithm: "); List<Integer> list = new ArrayList<>(); for (int i = end - count + 1; i < end; i++) { int random = NumberUtils.randomInteger(start, i); if (list.contains(random)) { list.add(i); } else { list.add(random); } } return list; } Test results:
Figure-2 Random number generation algorithm test results
In the above test results, we can clearly see that the naive random algorithm not only has duplicate data, but is also the most time-consuming. Therefore, avoid using this algorithm when generating sampled random numbers. Among the latter algorithms, the state transfer random algorithm is the best, and the iterative Floyd random algorithm is second. This can be made according to personal preferences.