preface

This is the sixth day of my participation in the First Challenge 2022

Speaking of snatching red envelopes, we must be very familiar with it, especially wechat snatching red envelopes, we will touch almost every day. Although each time grabbed the red envelope amount is big and small, but we are deeply immersed in the joy of grabbing red envelope 😄. But then again, I don’t know if you have thought about what algorithm is used to grab red envelopes? How does that happen? Today we find out…

Grab a red envelope

Now we give out red envelopes in no more than two forms: lucky red envelopes and fixed amount red envelopes. The number of fixed amount of red envelopes can be one or more, and the amount in each red envelope is the same, so there is no need to use too many algorithms to calculate the amount of red envelopes, relatively simple; But lucky red packets are more complicated, it needs to calculate the amount of each red packet, and ensure that each red packet is as fair as possible, which also requires a higher algorithm. Through searching Baidu and consulting friends who have achieved the red envelope snatching function, we learned that the algorithm with high frequency is the double mean method. Here we will use the double mean method to simulate the red envelope snatching function 👇

Through the double mean method to simulate snatching red envelopes

First of all, let’s look at the functional requirements of the lucky red envelope:

The total amount of all red packets is equal to the total amount of red packets
The amount of each red envelope must not be less than 0.01 yuan, that is, each user must ensure that at least one preset minimum amount can be grabbed, the minimum amount of RMB red envelope is set to 0.01 yuan, if other types of red envelope (such as points, other types of currency, etc.), you need to define a minimum amount
The expected revenue of snatching red packets should be independent of the order of snatching red packets, that is, the amount of each red packet is independent of the order of snatching red packets, so as to ensure that the red packets are as fair as possible

Before implementing the above functional requirements, we also need to know what is the double mean method 👇

If the total amount of red packets is X, the number of red packets is Y, and the minimum amount of each red packet is 0.01 yuan, then the amount of red packets snatched each time is in the range of (0.01, (X/Y) *2).

Let’s take a specific example, if there are 10 people snatching a red envelope of 100 yuan, then according to the above formula, the first person snatching the red envelope ranges from (0.01, 20), then according to the normal distribution, the first person snatching the red envelope should be around 10 yuan. And the probability of much less than 10 dollars and much more than 10 dollars is very low, so let’s just assume that the first person grabs 10 dollars; At this time, the second person to grab the red envelope, there is 90 yuan left in the red envelope, according to the formula, we can get that the second person to grab the red envelope amount range is (0.01, 20). By analogy, we can see that each person grabbed the red envelope amount of about 10 yuan, and the probability of much less than 10 yuan and much more than 10 yuan will be very low, so as to ensure that everyone grabbed the amount is similar.

Next, let’s look at the specific code 👇

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Random;

/** * Using the double mean method to simulate wechat grabbing red envelopes *@description: RedEnvelope
 * @author: Zhuang Ba. Liziye *@create: the 2022-02-15 for * * /
public class RedEnvelope {
    public static void main(String[] args) {
        long startTime=System.currentTimeMillis();
        // Initialize the test scenario to simulate four scenarios:
        //10 people grab a red envelope of 0.1 yuan
        //10 people grab a red envelope of 1 yuan
        //10 people grab a red envelope of 10 yuan
        //10 people grab a red envelope of 100 yuan
        BigDecimal[][] scene = {
                {new BigDecimal("0.1"), new BigDecimal("10")},
                {new BigDecimal("1"), new BigDecimal("10")},
                {new BigDecimal("10"), new BigDecimal("10")},
                {new BigDecimal("100"), new BigDecimal("10")}};// Set the minimum amount of each red envelope to 0.01 yuan
        BigDecimal min = new BigDecimal("0.01");
        // Test each red envelope separately
        for (BigDecimal[] decimals : scene) {
            final BigDecimal amount = decimals[0];
            final BigDecimal num = decimals[1];
            System.out.println("= = = = =" + num + "Grab one for yourself."+ amount + "Red envelope of yuan" + "= = = = =");
            GrabRedEnvelope(amount, min, num);
        }
        long endTime=System.currentTimeMillis();
        System.out.println("Program runtime:" + (endTime - startTime) + "ms");
    }

    // Simulate the process of snatching red packets
    private static void GrabRedEnvelope(BigDecimal amount, BigDecimal min, BigDecimal num){
        BigDecimal remain = amount.subtract(min.multiply(num));
        final Random random = new Random();
        final BigDecimal hundred = new BigDecimal("100");
        final BigDecimal two = new BigDecimal("2");
        BigDecimal sum = BigDecimal.ZERO;
        BigDecimal redpeck;
        for (int i = 0; i < num.intValue(); i++) {
            final int nextInt = random.nextInt(100);
            if(i == num.intValue() -1){
                redpeck = remain;
            }else{
                // roundingmode. CEILING: takes the nearest integer to the right
                // roundingmode. FLOOR: take the nearest positive number to the left
                redpeck = new BigDecimal(nextInt).multiply(remain.multiply(two).divide(num.subtract(new BigDecimal(i)),2, RoundingMode.CEILING)).divide(hundred,2, RoundingMode.FLOOR);
            }
            if(remain.compareTo(redpeck) > 0){
                remain = remain.subtract(redpeck);
            }else{
                remain = BigDecimal.ZERO;
            }
            sum = sum.add(min.add(redpeck));
            System.out.println("The first"+(i+1) +"The amount of red envelope grabbed by individuals is:"+min.add(redpeck));
        }
        System.out.println("Is the total amount of red envelopes equal to the total amount of red envelopes:"+compare(amount, sum));
    }

    private static boolean compare(BigDecimal a, BigDecimal b){
        if(a.compareTo(b) == 0) {return true;
        }
        return false; }}Copy the code

Let’s look at the result of the code 👇

= = = = =10Individual grab one0.1The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:0.01
第2The amount of red envelope grabbed by individuals is:0.01
第3The amount of red envelope grabbed by individuals is:0.01
第4The amount of red envelope grabbed by individuals is:0.01
第5The amount of red envelope grabbed by individuals is:0.01
第6The amount of red envelope grabbed by individuals is:0.01
第7The amount of red envelope grabbed by individuals is:0.01
第8The amount of red envelope grabbed by individuals is:0.01
第9The amount of red envelope grabbed by individuals is:0.01
第10The amount of red envelope grabbed by individuals is:0.01Is the total amount of red packets equal to the total amount of red packets:true= = = = =10Individual grab one1The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:0.06
第2The amount of red envelope grabbed by individuals is:0.11
第3The amount of red envelope grabbed by individuals is:0.14
第4The amount of red envelope grabbed by individuals is:0.10
第5The amount of red envelope grabbed by individuals is:0.06
第6The amount of red envelope grabbed by individuals is:0.06
第7The amount of red envelope grabbed by individuals is:0.10
第8The amount of red envelope grabbed by individuals is:0.02
第9The amount of red envelope grabbed by individuals is:0.13
第10The amount of red envelope grabbed by individuals is:0.22Is the total amount of red packets equal to the total amount of red packets:true= = = = =10Individual grab one10The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:1.61
第2The amount of red envelope grabbed by individuals is:1.08
第3The amount of red envelope grabbed by individuals is:1.45
第4The amount of red envelope grabbed by individuals is:1.35
第5The amount of red envelope grabbed by individuals is:1.02
第6The amount of red envelope grabbed by individuals is:0.57
第7The amount of red envelope grabbed by individuals is:0.11
第8The amount of red envelope grabbed by individuals is:1.16
第9The amount of red envelope grabbed by individuals is:1.31
第10The amount of red envelope grabbed by individuals is:0.34Is the total amount of red packets equal to the total amount of red packets:true= = = = =10Individual grab one100The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:10.19
第2The amount of red envelope grabbed by individuals is:9.38
第3The amount of red envelope grabbed by individuals is:14.47
第4The amount of red envelope grabbed by individuals is:2.08
第5The amount of red envelope grabbed by individuals is:2.98
第6The amount of red envelope grabbed by individuals is:12.42
第7The amount of red envelope grabbed by individuals is:13.81
第8The amount of red envelope grabbed by individuals is:19.87
第9The amount of red envelope grabbed by individuals is:8.58
第10The amount of red envelope grabbed by individuals is:6.22Is the total amount of red packets equal to the total amount of red packets:trueProgram running time: 6msCopy the code

We can see from the execution result that the two-fold mean method ensures the approximate amount of each red envelope as much as possible. And, of course, this algorithm also can’t be absolutely fair, or in accordance with 10 people grab a red envelope amount to 100 yuan, for example, if the first man grabbed 15 yuan, then the second personal bonus amount range becomes (0.01, 18.88), if at this time the second man robbed again high amount, that is bad for the people behind. As in the execution result above, 10 people grab the red envelope of 100 yuan, some grab 16.58, others grab 0.26😂.

In addition to the double means method, there is a more interesting algorithm – secant method, so let’s simply see what is secant method 👇

Through secant method to simulate snatching red envelopes

As the name suggests, the secant method treats the total amount of a red envelope as a piece of string, and then cuts the string. The length of each string represents the amount of each red envelope.

Here’s an example: Now there are 10 people snatching a 10 yuan red envelope, then there are 9 random numbers within the range of (0,10) with intervals greater than or equal to 0.01. Assuming that these 9 numbers are divided [1,1.6,2,3,4,5,6,7,8], then the size of each red envelope is 1, 0.6, 0.4,1,1,1,1,1,1,1,1,1,1,1,2.

Let’s take a look at the specific code 👇

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Random;

/** * Using secant method to simulate wechat snatching red envelopes *@description: RedEnvelope
 * @author: Zhuang Ba. Liziye *@create: the 2022-02-15 for * * /
public class RedEnvelope {
    public static void main(String[] args) {
        long startTime=System.currentTimeMillis();
        // Initialize the test scenario to simulate four scenarios:
        //10 people grab a red envelope of 0.1 yuan
        //10 people grab a red envelope of 1 yuan
        //10 people grab a red envelope of 10 yuan
        //10 people grab a red envelope of 100 yuan
        BigDecimal[][] scene = {
                {new BigDecimal("0.1"), new BigDecimal("10")},
                {new BigDecimal("1"), new BigDecimal("10")},
                {new BigDecimal("10"), new BigDecimal("10")},
                {new BigDecimal("100"), new BigDecimal("10")}};// Set the minimum amount of each red envelope to 0.01 yuan
        BigDecimal min = new BigDecimal("0.01");
        // Test each red envelope separately
        for (BigDecimal[] decimals : scene) {
            final BigDecimal amount = decimals[0];
            final BigDecimal num = decimals[1];
            System.out.println("= = = = =" + num + "Grab one for yourself."+ amount + "Red envelope of yuan" + "= = = = =");
            GrabRedEnvelope(amount, min, num);
        }
        long endTime=System.currentTimeMillis();
        System.out.println("Program runtime:" + (endTime - startTime) + "ms");
    }

    // Simulate the process of snatching red packets
    private static void GrabRedEnvelope(BigDecimal amount,BigDecimal min ,BigDecimal num){
        final Random random = new Random();
        final int[] rand = new int[num.intValue()];
        BigDecimal sum1 = BigDecimal.ZERO;
        BigDecimal redpeck ;
        int sum = 0;
        for (int i = 0; i < num.intValue(); i++) {
            rand[i] = random.nextInt(100);
            sum += rand[i];
        }
        final BigDecimal bigDecimal = new BigDecimal(sum);
        BigDecimal remain = amount.subtract(min.multiply(num));
        for (int i = 0; i < rand.length; i++) {
            if(i == num.intValue() -1){
                redpeck = remain;
            }else{
                redpeck = remain.multiply(new BigDecimal(rand[i])).divide(bigDecimal,2,RoundingMode.FLOOR);
            }
            if(remain.compareTo(redpeck) > 0){
                remain = remain.subtract(redpeck);
            }else{
                remain = BigDecimal.ZERO;
            }
            sum1= sum1.add(min.add(redpeck));
            System.out.println("The first"+(i+1) +"The amount of red envelope grabbed by individuals is:"+min.add(redpeck));
        }

        System.out.println("Is the total amount of red envelopes equal to the total amount of red envelopes:" + compare(amount, sum1));
    }

    private static boolean compare(BigDecimal a, BigDecimal b){
        if(a.compareTo(b) == 0) {return true;
        }
        return false; }}Copy the code

Next, take a look at the secant method’s execution result 👇

= = = = =10Individual grab one0.1The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:0.01
第2The amount of red envelope grabbed by individuals is:0.01
第3The amount of red envelope grabbed by individuals is:0.01
第4The amount of red envelope grabbed by individuals is:0.01
第5The amount of red envelope grabbed by individuals is:0.01
第6The amount of red envelope grabbed by individuals is:0.01
第7The amount of red envelope grabbed by individuals is:0.01
第8The amount of red envelope grabbed by individuals is:0.01
第9The amount of red envelope grabbed by individuals is:0.01
第10The amount of red envelope grabbed by individuals is:0.01Is the total amount of red packets equal to the total amount of red packets:true= = = = =10Individual grab one1The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:0.07
第2The amount of red envelope grabbed by individuals is:0.12
第3The amount of red envelope grabbed by individuals is:0.01
第4The amount of red envelope grabbed by individuals is:0.10
第5The amount of red envelope grabbed by individuals is:0.10
第6The amount of red envelope grabbed by individuals is:0.08
第7The amount of red envelope grabbed by individuals is:0.06
第8The amount of red envelope grabbed by individuals is:0.06
第9The amount of red envelope grabbed by individuals is:0.04
第10The amount of red envelope grabbed by individuals is:0.36Is the total amount of red packets equal to the total amount of red packets:true= = = = =10Individual grab one10The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:1.19
第2The amount of red envelope grabbed by individuals is:1.01
第3The amount of red envelope grabbed by individuals is:0.60
第4The amount of red envelope grabbed by individuals is:0.69
第5The amount of red envelope grabbed by individuals is:0.66
第6The amount of red envelope grabbed by individuals is:0.44
第7The amount of red envelope grabbed by individuals is:0.39
第8The amount of red envelope grabbed by individuals is:0.62
第9The amount of red envelope grabbed by individuals is:0.41
第10The amount of red envelope grabbed by individuals is:3.99Is the total amount of red packets equal to the total amount of red packets:true= = = = =10Individual grab one100The red envelope of yuan ===== the first1The amount of red envelope grabbed by individuals is:17.51
第2The amount of red envelope grabbed by individuals is:14.62
第3The amount of red envelope grabbed by individuals is:2.47
第4The amount of red envelope grabbed by individuals is:4.19
第5The amount of red envelope grabbed by individuals is:8.63
第6The amount of red envelope grabbed by individuals is:0.01
第7The amount of red envelope grabbed by individuals is:0.23
第8The amount of red envelope grabbed by individuals is:6.15
第9The amount of red envelope grabbed by individuals is:3.66
第10The amount of red envelope grabbed by individuals is:42.53Is the total amount of red packets equal to the total amount of red packets:trueProgram running time: 11msCopy the code

Through the implementation of the results we can see that secant method of randomness is relatively large, and can not ensure that the amount of each red envelope is roughly similar (10 people grab a 100 yuan red envelope, and some people will grab 0.01, which can not give people angry 😂); The secant method also does not perform very well. Although the above code shows that the execution time of the two-fold mean method and the secant method is not different, the difference must be huge when there is a large number of red packets to calculate in the production environment. So we want to achieve the function of snatching red packets must carefully consider, choose a can guarantee the amount of similar and can ensure efficient algorithm oh ~

summary

My experience is limited, some places may not be particularly in place, if you think of any questions when reading, welcome to leave a message in the comments section, we will discuss one by one 🙇

Please take a thumbs up and a follow (✿◡‿◡) for this article ~ a crab (●’◡’●)

If there are mistakes in the article, welcome to comment correction; If you have a better, more unique understanding, you are welcome to leave your valuable ideas in the comments area.

Love what you love, do what you do, listen to your heart and ask nothing

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Great wisdom to teach you to learn Java | WeChat grab a red envelope is simulated by two times the average method

preface

Grab a red envelope

Through the double mean method to simulate snatching red envelopes

Through secant method to simulate snatching red envelopes

summary

Great wisdom to teach you to learn Java | WeChat grab a red envelope is simulated by two times the average method

preface

Grab a red envelope

Through the double mean method to simulate snatching red envelopes

Through secant method to simulate snatching red envelopes

summary

Related Posts

Centos VM clone. If the newly cloned server is placed on the same VM, the new VM cannot be used

Druid source code (8)

Java background programmer to Android “3” integration of Tencent Yunyun Live broadcast push stream end, accept the display end, background server end and pit mining records