This article is shared from Huawei cloud community “Why the Spring Festival is not always the best luck? After reading wechat red envelope algorithm you will understand!” , the author is XiaoLin_Java.

preface

From the previous paper red envelopes to the Internet red envelopes (led by wechat red envelopes), snatching red envelopes is popular with all people. Today we will analyze the algorithm to grab the red envelope, some of which are wechat red envelope algorithm, after reading you will know how to produce the best luck!

Algorithm 1: random residual amount method

Algorithm 1 is not recommended. The full name of algorithm 1 is residual amount random method. It can be seen from the name that this method is to randomly allocate the residual amount.

Private static void testPocket(BigDecimal amount, BigDecimal min, BigDecimal num) { BigDecimal remain = amount.subtract(min.multiply(num)); final Random random = new Random(); final BigDecimal hundred = new BigDecimal("100"); 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 { redpeck = new BigDecimal(nextInt).multiply(remain).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(" "+ (I + 1) +" + min.add(redpeck).setscale (2, BigDecimal.ROUND_HALF_UP)); } system.out. println(" sum. SetScale (2, BigDecimal.ROUND_HALF_UP)); } public static void main(String[] args) {BigDecimal Amount = new BigDecimal(100).setScale(2, BigDecimal.ROUND_HALF_UP); ROUND_HALF_UP BigDecimal min = new BigDecimal(0.01).setScale(2, BigDecimal.ROUND_HALF_UP); BigDecimal num = new BigDecimal(10).setScale(2, BigDecimal.ROUND_HALF_UP); testPocket2(amount,min,num); }Copy the code

We can see that this method has obvious defects, that is, at the beginning, the person who gets the red envelope may get the largest amount, and then the amount gets smaller, because he is random from the remaining amount. Obviously wechat is certainly not using this method as a red envelope partition algorithm, otherwise every time there is a red envelope, immediately get it is possible to get the best luck, but obviously not.

Algorithm two: the whole random method

The formula of total amount randomization method is: total amount of red envelopes * Random number/sum of Random numbers. The core of this method is to use a Random number as the standard for dividing red envelopes, which is randomly generated by the Random class. His randomness is relatively large, it looks like it is about the same as we usually grab red envelopes, but wechat red envelopes are not used in this way, because this randomness is too large, not very fair.

private static void testPocket2(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)).setScale(2, BigDecimal.ROUND_HALF_UP); System.out.println(" "+(I +1)+" +min.add(redpeck).setscale (2, BigDecimal.ROUND_HALF_UP)); } system.out. println(" sum: "+sum1); } public static void main(String[] args) {BigDecimal Amount = new BigDecimal(100).setScale(2, BigDecimal.ROUND_HALF_UP); ROUND_HALF_UP BigDecimal min = new BigDecimal(0.01).setScale(2, BigDecimal.ROUND_HALF_UP); BigDecimal num = new BigDecimal(10).setScale(2, BigDecimal.ROUND_HALF_UP); testPocket2(amount,min,num); }Copy the code

He is highly random and not the best choice.

Algorithm three: secant line method

Secant line method is to imagine the total amount of the red envelope as a long line segment, and the amount of money grabbed by each person is a number of sub-line segments separated from the main line segment. When all the cutting points are determined, the length of the sub-line segment is also determined. In this way, when each person comes to grab a red envelope, they only need to get the red envelope amount equal to the length of the subline.

private static void testPocket3(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).setScale(2, BigDecimal.ROUND_HALF_UP); } else { remain = BigDecimal.ZERO; } sum1 = sum1.add(min.add(redpeck).setScale(2, BigDecimal.ROUND_HALF_UP)); System.out.println(" "+ (I + 1) +" "+ min.add(redpeck)); } system.out. println(" sum: "+ sum1); } public static void main(String[] args) {BigDecimal Amount = new BigDecimal(100).setScale(2, BigDecimal.ROUND_HALF_UP); ROUND_HALF_UP BigDecimal min = new BigDecimal(0.01).setScale(2, BigDecimal.ROUND_HALF_UP); BigDecimal num = new BigDecimal(10).setScale(2, BigDecimal.ROUND_HALF_UP); testPocket2(amount,min,num); }Copy the code

He also has a lot of randomness, but his most lethal feature is performance, because he needs to perform the cutting step.

Algorithm four: double mean method

Algorithm 4 is the algorithm currently used in wechat red envelope (general idea, code simulation), the double mean calculation formula: 2 * the remaining amount/the number of remaining red envelope.

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{ 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).setScale(2, BigDecimal.ROUND_HALF_UP); }else{ remain = BigDecimal.ZERO; } sum = sum.add(min.add(redpeck)).setScale(2, BigDecimal.ROUND_HALF_UP); System.out.println(" "+(I +1)+" "+min.add(redpeck)); } system.out. println(" sum: "+ sum); }Copy the code

It is better to ensure that the amount of each red packet is roughly equal, and there will be no extreme cases.

Click to follow, the first time to learn about Huawei cloud fresh technology ~