我与随机红包算法的故事

我与随机红包算法的故事

背景故事：

1. 期初，为了快速实现，我采用的算法是只要满足最小值，可以分配完金额，并且不超额即可 （算法一）
2. 中期，发现算法一有个严重的问题，越往后领取红包，金额越小，并且后面出现大量的最小值问题，使用 N 倍均值法解决（算法二）
3. 后期，加入领取红包最大值的控制条件，只允许每个红包的最大金额为 200 元（算法三）
4. 以下说明，均为算法三的。细细品算法三，就能看到算法二与算法一的影子

算法要点：

1. 满足：红包的总金额 === 领取红包总额
2. 满足：红包的总金额 ≥ 红包最小金额 * 领取红包的人数
3. 满足：红包的总金额 ≤ 红包最大金额 * 领取红包的人数
4. 满足：红包领取的最小金额 ≤ 红包领取的最大金额

算法分析：

1. 计算随机值：每一个随机值，都是在最小值与最大值之间取一个值出来的（apportion 方法）
2. 计算最小值：在没有最大值时，可以直接使用传入的最小值；如果有，就需要考虑其他次数都获取到最大值后所剩下的值的情况。如果剩下的值 ＞ 初始最小值，那它替代掉初始最小值（calcMin 方法）
3. 计算最大值：计算最大值方法需要的最小值，必须是上一步计算出来的最小值。最大值的计算，是整个算法的核心所在。为了值分布得均匀一些，我们使用的是N倍均值算法。计算出平均值，然后乘以倍率，即可得出最大值。计算出来的最大值，还必须小于等于其他次数领取到最小值后剩下的值（calcMax 方法）
4. 为了方便计算，代码使用了以分为单位，并在最后格式化输出
5. 好羞涩难懂的表述啊，还是直接上算法代码吧

算法使用：

//例子： 发一个100元的红包，10个人领取，最小领取 0.01 元，最大领取金额为 5 元，均值倍率为 2倍，以元的方式输出
$amount = 10000;
$count = 10;
$min = 1;
$max = 500;
$avgMultiple = 2;
$needFormat = true;
$service = new DivideCandyService($amount,$count,$min,$max,$avgMultiple,$needFormat);
$values = $service->handle();
1
2
3
4
5
6
7
8
9

算法代码（php）：

/**
 * 分糖果算法（随机红包算法）
 */
class DivideCandyService
{
    /**
     * 总糖果数
     *
     * @var int
     */
    protected $amount;

    /**
     * 分糖人数
     *
     * @var int
     */
    protected $count;

    /**
     * 领取的最少个数
     *
     * @var int
     */
    protected $min;

    /**
     * 领取的最多个数
     *
     * @var int
     */
    protected $max;


    /**
     * 均值倍率
     *
     * @var float
     */
    protected $avgMultiple;

    /**
     * 是否需要格式化输出（除以100）
     *
     * @var bool
     */
    protected $needFormat;

    /**
     * 结果值
     *
     * @var array
     */
    protected $items = [];



    public function __construct(
        int $amount,
        int $count = 1,
        int $min = 1,
        int $max = 0,
        float $avgMultiple = 2,
        bool $needFormat = true
    ) {
        $this->amount      = $amount;
        $this->count       = $count;
        $this->min         = $min;
        $this->max         = $max;
        $this->avgMultiple = $avgMultiple;
        $this->needFormat  = $needFormat;
    }

    /**
     * 处理返回
     *
     * @return array
     * @throws \Exception
     */
    public function handle()
    {
        //验证最小值
        $totalMin = $this->min * $this->count;
        if ($this->amount < $totalMin) {
            throw new \Exception('总数太小了');
        }

        //验证最大值
        if ($this->max > 0) {
            $totalMax = $this->max * $this->count;
            if ($this->amount > $totalMax) {
                throw new \Exception('总数太大了');
            }
        }

        //随机分配
        $this->apportion();

        return $this->items;
    }

    /**
     * 分配红包
     */
    protected function apportion()
    {
        $count  = $this->count;
        $amount = $this->amount;

        while ($count >= 1) {
            //最后一个，直接取值
            if ($count === 1) {
                $randomValue = $amount;
            } else {
                $calcMin     = $this->calcMin($amount, $count, $this->min, $this->max);
                $calcMax     = $this->calcMax($amount, $count, $calcMin, $this->max);
                $randomValue = random_int($calcMin, $calcMax);
            }

            //追加分配
            $this->items[] = $this->formatValue($randomValue);

            $amount -= $randomValue;
            --$count;
        }

        //随机打乱
        shuffle($this->items);
    }


    /**
     * 计算最小值
     *
     * @param int $amount
     * @param int $count
     * @param int $min
     * @param int $max
     *
     * @return int
     */
    protected function calcMin(int $amount, int $count, int $min, int $max): int
    {
        //没有最大值的限制，可以直接输出最小值
        if ($max <= 0) {
            return $min;
        }

        $otherTotalMax = ($count - 1) * $max;
        $newMin        = $amount - $otherTotalMax;
        if ($newMin > $min) {
            return $newMin;
        }

        return $min;
    }

    /**
     * 计算最大值
     *
     * @param int $amount
     * @param int $count
     * @param int $min
     * @param int $max
     *
     * @return int
     */
    protected function calcMax(int $amount, int $count, int $min, int $max): int
    {
        $totalMin = $min * $count;

        if ($amount <= $totalMin) {
            return $min;
        }

        //可领取的最大值： 总值 - 其他人都领取最小值的总和
        $otherTotalMin = ($count - 1) * $min;
        $calcAmount    = $amount - $otherTotalMin;

        //人均最大值
        $avg     = $amount / $count;
        $calcMax = (int)($avg * $this->avgMultiple);
        $calcMax = $calcMax > $calcAmount ? $calcAmount : $calcMax;

        if ($max <= 0 || ($calcMax <= $max && $calcMax >= $min)) {
            return $calcMax;
        }

        return $max;
    }


    /**
     * 格式化
     */
    protected function formatValue(int $value)
    {
        if ($this->needFormat) {
            return (float)bcdiv((string)$value, '100', 2);
        }

        return $value;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205