A variety of algorithms for generating sampling random numbers in Java

This chapter first explains several ways of generating java random numbers, and then demonstrates them through examples.

summary:

Would you say here, what is the difficulty of generating random numbers? Isn't it just to use the Java encapsulated random directly? Of course, it is OK in general, and the algorithms to be described in this paper are also based on this random library function.

This paper mainly focuses on the behavior of sampling, and sampling itself has an implicit rule that there should be no duplicate data. Well, with these instructions. You can try to use some of your own ideas to generate random numbers without repetition.

Algorithm attempt:

Some good algorithms appear, often accompanied by some not so good algorithms. However, for the algorithms with poor results, they generally have a common feature, which is convenient to understand and implement. The following is a simple explanation in a step-by-step way.

First attempt: naive random algorithm

This algorithm is easy to understand, is random! Each time a random number is generated and added to the set.

Second attempt: check the existence of random algorithm

We know that there is a problem with the above method, that is, there may be duplicate data. Therefore, we thought that when generating a random number, check whether the number already exists, and if so, regenerate it.

Third attempt: element removal random algorithm

The above algorithm has solved the problem of data duplication. However, a bad problem is that it may take us a long time to generate sampling random numbers (it depends on the face...).

But here we have new ideas. That is to random a number in a set, and remove it when it is selected. Will it not be random to this number next time? In this way, the problem of repetition of random numbers is well solved. The code is as follows:

Fourth attempt: state transition random algorithm

In many of my previous blogs, there are some state transition processes in the algorithm. State transition is also one of my favorite algorithms. The value range of random number is marked in figure-1 below, and the orange number in the sequence is the random sequence in the result. There are some dashed arrows in the bottom sequence, representing the transition of state.

Figure-1 sampling random number generation algorithm based on state transition

Implementation code:

Fifth attempt: recursive Floyd random algorithm

Floyd algorithm is also a state transition process in the final analysis. The algorithm will require you to enter a list or array to save the determined random number. As the name suggests, I will use the recursive solution here. In the process of recursion, we transfer the state of the i-th random number to the i-1st random number. The code is as follows:

Sixth attempt: iterative 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. The code is as follows:

Test results:

Figure 2 test results of random number generation algorithm

In the above test results, we can clearly see that the naive random algorithm not only has duplicate data, but also is the most time-consuming. Therefore, avoid using this algorithm when generating random numbers of sampling. Among the latter algorithms, the state transition random algorithm is the best, followed by the iterative Floyd random algorithm. This can be chosen according to personal preference.