微信红包算法研究

背景：之前过年亲戚人都在抢红包，都想抢第一个，说是越早抢越大。其实这肯定是不正确的，微信在你发红包的时候应该已经生成所有的红包了，所以说你无论第几个抢，按说应该都一样，除非微信做了一些处理，比如说越早抢红包越可能手气最佳，过完年回来上班，突然想起了微信红包，就在想微信红包生成的策略。

20块钱10个红包，人均2块钱。因为理论上红包的金额应该在2块钱左右，而且越大概率越小，感觉这个很像正态分布函数，所以感觉微信红包属于截尾正态分布。手气最佳一般在2倍-3倍左右。
类似于这种(网上找的图):

所有红包在发送者发红包的时候都已经生成好了，领红包只是领生成的红包而已，点击别人发的红包，只会计算你点击的那一时刻还有没有红包，如果没有了，你就只能查看details了，所以说打开的时候出现的那个拆字相当于一个令牌，你可以凭借这个令牌去领红包，当然这个令牌在领红包的时候也有可能红包被领完了，所以你也就回去看details了，如果领到了就会告诉你领了多少钱。

每一次从红包金额池里随机出的金额应该是当时剩余总人数的均值，比如第一个人抽应该基于2的正态分布，如果他抽了4块钱，那么随机第二个红包的时候自然是基于16/9的正态分布，以此往后推，抽到倒数第一个就不用抽了，直接把剩下的都分了就行。而且因为红包最小是0.01嘛，所以每一次抽奖的时候都得留够足够的钱来用于发放剩下的红包，随意每一次随机都得判断。而且我做了一个限额倍数，因为随机出来的数字很可能在均值偏下的地方，多个累积起来，很可能就会造成最后一个红包过大的可能，所以我做了调整，当最后一个红包大于一定的倍数的时候，需要重新抽。另外，按这样抽奖，第一个人的均值应该最大，所以我在最后对生成的红包打乱了顺序。

随机生成红包的代码，做了一些简单的封装。
若Y～N(a,b^2) (b>0)，则X=(Y-a)/b～(0,1)

package com.galaxy.fym.algorithm.maxsublist;

import java.math.BigDecimal;
import java.util.*;

/**
 * Created by fengyiming on 2017/2/17.
 *
 * @author fengyiming
 *         随机产生红包：金额正太分布
 *
 *         如果非标准正态分布X~N(μ,σ^2)，那么关于X的一个一次函数 (X-μ)/σ ，就一定是服从标准正态分布N(0,1)。
 *         举个具体的例子，一个量X，是非标准正态分布，期望是10，方差是5^2（即X~N(10,5^2)）；那么对于X的线性函数Y=(X-10)/5，Y就是服从标准正态分布的Y~N(0,1)。
 */
public class RedPacket {

    private static Random random = new Random();

    private static BigDecimal MIN_VALUE = new BigDecimal("0.01");

    private static boolean isMin = false;

    /**
     * 生成红包
     *
     * @param amountValue 红包总金额
     * @param sizeValue   红包大小
     * @param maxMutValue 剩余红包限定倍数
     * @param sigmaValue  标准差倍数
     * @return
     */
    public static List<BigDecimal> getAllHotPacket(double amountValue, double sizeValue, double maxMutValue, double sigmaValue) {
        //红包总金额
        BigDecimal amount = new BigDecimal(String.valueOf(amountValue));
        BigDecimal restAmount = amount;
        BigDecimal size = new BigDecimal(String.valueOf(sizeValue));
        BigDecimal mu = restAmount.divide(size, 2, BigDecimal.ROUND_HALF_DOWN);
        BigDecimal avg = new BigDecimal(mu.toString());
        BigDecimal MAX_MUT = new BigDecimal(String.valueOf(maxMutValue));
        double sigma = sigmaValue <= 0 ? 1 : sigmaValue;
        List<BigDecimal> hotPacketPool;
        do {
            hotPacketPool = new ArrayList<BigDecimal>(size.intValue());
            int hotPacketSize = size.intValue() - 1;
            //随机出前size-1个红包，最后一个红包取剩余值，并且最后一个红包不能过大，有均值的限定倍数
            for (int i = 0; i < hotPacketSize; i++) {
                BigDecimal randomBigDecimal = getRandomHotPacketAmount(mu.doubleValue(), sigma, restAmount, size.intValue()-1);
                restAmount = restAmount.subtract(randomBigDecimal);
                //System.out.println("剩下的红包金额：" + restAmount);
                size = size.subtract(BigDecimal.ONE);
                mu = restAmount.divide(size, 2, BigDecimal.ROUND_HALF_DOWN);
                hotPacketPool.add(randomBigDecimal);
            }
            hotPacketPool.add(restAmount);
        } while (restAmount.compareTo(avg.multiply(MAX_MUT)) > 0);
        //打乱红包顺序，因为越早的红包均值最高
        //倒序遍历list，然后在当前位置随机一个比当前位置小的int数字，交换数字
        Collections.shuffle(hotPacketPool);
        return hotPacketPool;
    }

    /**
     * 根据剩余红包金额均值，标准差大小，计算出随机红包的大小
     *
     * @param mu
     * @param sigma
     * @param rest 剩下的钱
     * @param restSize 还剩多少红包
     * @return
     */
    private static BigDecimal getRandomHotPacketAmount(double mu, double sigma, BigDecimal rest, int restSize) {
        if(isMin){
            return MIN_VALUE;
        }
        BigDecimal radomNo;
        //剩余最小的钱
        BigDecimal minRest = MIN_VALUE.multiply(new BigDecimal(restSize));
        //随机出的红包也得满足剩余红包最少0.01
        do {
            radomNo = getRandom(mu, mu * sigma);
        }
        while (rest.subtract(radomNo).subtract(minRest).compareTo(BigDecimal.ZERO) < 0);
        if(rest.subtract(radomNo).subtract(minRest).compareTo(BigDecimal.ZERO) == 0){
            isMin = true;
        }
        BigDecimal randomBigDecimal = radomNo;
        //对红包金额取2位小数
        randomBigDecimal = randomBigDecimal.setScale(2, BigDecimal.ROUND_HALF_DOWN);
        //判断金额不能小于0.01元
        randomBigDecimal = randomBigDecimal.compareTo(MIN_VALUE) > 0 ? randomBigDecimal : MIN_VALUE;
        return randomBigDecimal;
    }

    /**
     * 产生mu sigma的正态分布的double值
     *
     * @param mu
     * @param sigma
     * @return
     */
    private static BigDecimal getRandom(double mu, double sigma) {
        double randomValue = random.nextGaussian() * sigma + mu;
        BigDecimal value = new BigDecimal(String.valueOf(randomValue)).abs();
        return value;
    }

    public static void main(String[] args) {
        BigDecimal all = BigDecimal.ZERO;
        List<BigDecimal> allHotPacket = getAllHotPacket(10d, 10d, 3d, 1d);
        int size = allHotPacket.size();
        BigDecimal max = BigDecimal.ZERO;
        int maxIndex = 0;
        for (int i = 0; i < size; i++) {
            BigDecimal amout = allHotPacket.get(i);
            System.out.println("第" + (i + 1) + "随机的红包金额大小：" + amout);
            if (amout.compareTo(max) > 0) {
                max = amout;
                maxIndex = i + 1;
            }
            all = all.add(amout);
        }
        System.out.println("所有红包金额为红包：" + all);
        System.out.println("手气最佳为：第" + maxIndex + "个红包，金额为：" + max);
    }

}

第1随机的红包金额大小：0.15
第2随机的红包金额大小：1.48
第3随机的红包金额大小：0.02
第4随机的红包金额大小：2.21
第5随机的红包金额大小：1.14
所有红包金额为红包：5.00
手气最佳为：第4个红包，金额为：2.21

第1随机的红包金额大小：0.13
第2随机的红包金额大小：0.65
第3随机的红包金额大小：2.30
第4随机的红包金额大小：0.95
第5随机的红包金额大小：0.97
所有红包金额为红包：5.00
手气最佳为：第3个红包，金额为：2.30

第1随机的红包金额大小：4.74
第2随机的红包金额大小：0.88
第3随机的红包金额大小：1.07
第4随机的红包金额大小：0.20
第5随机的红包金额大小：0.43
第6随机的红包金额大小：0.41
第7随机的红包金额大小：0.22
第8随机的红包金额大小：0.20
第9随机的红包金额大小：0.65
第10随机的红包金额大小：1.20
所有红包金额为红包：10.00
手气最佳为：第1个红包，金额为：4.74

第1随机的红包金额大小：0.63
第2随机的红包金额大小：0.33
第3随机的红包金额大小：1.35
第4随机的红包金额大小：1.00
第5随机的红包金额大小：0.70
第6随机的红包金额大小：3.19
第7随机的红包金额大小：0.19
第8随机的红包金额大小：1.50
第9随机的红包金额大小：0.18
第10随机的红包金额大小：0.93
所有红包金额为红包：10.00
手气最佳为：第6个红包，金额为：3.19

第1随机的红包金额大小：1.05
第2随机的红包金额大小：0.68
第3随机的红包金额大小：0.19
第4随机的红包金额大小：1.64
第5随机的红包金额大小：1.64
第6随机的红包金额大小：0.86
第7随机的红包金额大小：0.81
第8随机的红包金额大小：1.06
第9随机的红包金额大小：0.98
第10随机的红包金额大小：1.09
所有红包金额为红包：10.00
手气最佳为：第4个红包，金额为：1.64

测试随机数是否符合正态分布

package com.galaxy.fym.algorithm.maxsublist;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * Created by fengyiming on 2017/2/19.
 * 验证是否符合正态分布的算法
 */
public class Test2 {

    private static Random random = new Random();

    private final static double[] sigmas = {1d, 2d, 3d};

    private final static double DOUBLE_1 = 1d;

    private final static double DOUBLE_0 = 0d;

    public static void main(String[] args) {
        int size = 10000000;
        double mu = 2d;
        double sigmaValue = 1d;
        //标准差的切换
        double sigma = mu * sigmaValue;
        Map<Double, Double> map = installMap();
        for (int i = 0; i < size; i++) {
            double radomNo = getRandom(mu, sigma);
            if (radomNo > mu - sigma && radomNo <= mu + sigma) {
                map.put(sigmas[0], map.get(sigmas[0]) + DOUBLE_1);
            }
            if (radomNo > mu - 2  sigma && radomNo <= mu + 2  sigma) {
                map.put(sigmas[1], map.get(sigmas[1]) + DOUBLE_1);
            }
            if (radomNo > mu - 3  sigma && radomNo <= mu + 3  sigma) {
                map.put(sigmas[2], map.get(sigmas[2]) + DOUBLE_1);
            }
        }
        double mu1 = map.get(sigmas[0]);
        double mu2 = map.get(sigmas[1]);
        double mu3 = map.get(sigmas[2]);
        System.out.println("随机数出现在1个标注差内的概率为：" + mu1 / size);
        System.out.println("随机数出现在2个标注差内的概率为：" + mu2 / size);
        System.out.println("随机数出现在3个标注差内的概率为：" + mu3 / size);

    }

    private static double getRandom(double mu, double sigma) {
        return random.nextGaussian() * sigma + mu;
    }

    private static Map<Double, Double> installMap() {
        Map<Double, Double> map = new HashMap();
        map.put(sigmas[0], DOUBLE_0);
        map.put(sigmas[1], DOUBLE_0);
        map.put(sigmas[2], DOUBLE_0);
        return map;
    }
}

当然，微信红包肯定不是这么简单，也有可能不是基于正态分布，所以为了增加他的可玩性，应该做了很多的处理，比如说在红包均值很高的时候总有一些人会出现好几个几分的，这个估计应该是做了处理的。