【算法】抽奖算法

发表于 阅读次数：

抽奖算法理论

在一组奖品中，每个奖品有自己的概率，总概率为 1.0，也就是说在库存充足的情况下，必然能抽中其中的一个。

通过「谢谢参与」来作为无奖的奖品（也是一种奖品）。

需要注意的是：如果一组中所有的奖品，总概率之和不为 1.0，那么数值代表的概率就不是真实概率了，需要用所占比例来作为新的概率：新概率值=奖品概率/总概率。

举个例子：只有 A 和 B 两个奖品，A 概率是 0.1，B 概率是 0.3，那么总概率就是 0.4，A 的真实概率就是0.1/0.4=0.25，B 的真实概率是0.3/0.4=0.75，真实的总概率依然为1。

所以如果想要配置的奖品概率正好是抽奖时的概率值，那么就需要为这一组奖品列表的总概率配置成1.0；

实现

首先定义一个有概率的奖品基类，所有继承这个基类的子类，都可以用调用 LotteryTool.draw 算法（draw 中的参数类型使用了java泛型）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import lombok.Getter;
import lombok.Setter;

/**
 * 奖品基类
 *
 */
@Setter
@Getter
public class BaseAward {
    /**
     * 抽中这个奖品的概率
     */
    private Double probability;
}

接着是具体的奖品类

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
import lombok.Getter;
import lombok.Setter;
import lombok.ToString;

/**
 * 奖品实现类
 */
@Setter
@Getter
@ToString
public class Award extends BaseAward {
    private Integer id;
    private String name;
    private Double price;
    private Integer stock;

    public Award(Integer id, String name, Double price, Double probability, Integer stock) {
        super();
        this.id = id;
        this.name = name;
        this.price = price;
        this.stock = stock;
        setProbability(probability);
    }
}

看看抽奖的工具类

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
import cn.hutool.core.collection.CollUtil;
import cn.hutool.core.util.RandomUtil;

import java.util.List;

/**
 * 抽奖工具类
 */
public class LotteryTool {

    /**
     * 抽奖方法
     *
     * @param awardList 奖品列表，这些是备选的奖品（一定有库存的）
     * @param <T>       具体奖品类型
     * @return 返回一个抽中的奖品
     */
    public static <T extends BaseAward> T draw(List<T> awardList) {
        if (CollUtil.isEmpty(awardList)) {
            return null;
        }

        // 获取总概率，当奖品总概率正好为1时，奖品的 probability 就是真实的概率，否则会按新的比例作为概率
        double sumProbability = awardList.stream()
                .map(BaseAward::getProbability)
                .reduce(0.0, Double::sum);

        // 一共会尝试 awardList.size() 次，确保能返回一个奖品
        for (T t : awardList) {

            // 使用随机值，左闭右开（包含0，不包含1）
            if (t.getProbability() > RandomUtil.randomDouble(0.0, 1.0) * sumProbability) {
                return t;
            }
            sumProbability = sumProbability - t.getProbability();
        }

        // 其它情况，会到这里（理论上，一定到不了这里的。）
        return null;
    }
}

最后来个测试

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

import cn.hutool.core.util.StrUtil;

import java.util.ArrayList;
import java.util.List;
/**
* 测试
*/
public class Main {
    public static void main(String[] args) {
        // 奖品列表，库存一共36
        final List<Award> awardList = new ArrayList<>(4);
        awardList.add(new Award(1, "苹果手机", 7000.0, 0.05, 1));
        awardList.add(new Award(2, "5元金币", 5.0, 0.1, 5));
        awardList.add(new Award(3, "15元天堂雨伞", 15.0, 0.25, 10));
        awardList.add(new Award(4, "谢谢参与", 0.0, 0.6, 20));

        System.out.println("开始抽奖:");
        // 抽奖50次
        for (int i = 0; i < 50; i++) {
            String msg;
            final Award draw = LotteryTool.draw(awardList);
            if (draw == null) {
                msg = "奖品抽完了，下次早点来吧~";
            } else {
                msg = StrUtil.format("抽到了价值「{}」的奖品「{}」", draw.getPrice(), draw.getName());

                // 抽到奖品了，需要减库存，库存不足了，要从列表中剔除
                draw.setStock(draw.getStock() - 1);
                if (draw.getStock() <= 0) {
                    awardList.remove(draw);
                }
            }

            System.out.println(StrUtil.format("第{}次抽奖，结果为：{}", i+1, msg));
        }
        System.out.println("抽奖结束.");
    }
}
/*output~
开始抽奖:
第1次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第2次抽奖，结果为：抽到了价值「5.0」的奖品「5元金币」
第3次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第4次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第5次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第6次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第7次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第8次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第9次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第10次抽奖，结果为：抽到了价值「5.0」的奖品「5元金币」
第11次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第12次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第13次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第14次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第15次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第16次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第17次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第18次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第19次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第20次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第21次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第22次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第23次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第24次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第25次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第26次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第27次抽奖，结果为：抽到了价值「0.0」的奖品「谢谢参与」
第28次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第29次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第30次抽奖，结果为：抽到了价值「5.0」的奖品「5元金币」
第31次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第32次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第33次抽奖，结果为：抽到了价值「5.0」的奖品「5元金币」
第34次抽奖，结果为：抽到了价值「15.0」的奖品「15元天堂雨伞」
第35次抽奖，结果为：抽到了价值「5.0」的奖品「5元金币」
第36次抽奖，结果为：抽到了价值「7000.0」的奖品「苹果手机」
第37次抽奖，结果为：奖品抽完了，下次早点来吧~
第38次抽奖，结果为：奖品抽完了，下次早点来吧~
第39次抽奖，结果为：奖品抽完了，下次早点来吧~
第40次抽奖，结果为：奖品抽完了，下次早点来吧~
第41次抽奖，结果为：奖品抽完了，下次早点来吧~
第42次抽奖，结果为：奖品抽完了，下次早点来吧~
第43次抽奖，结果为：奖品抽完了，下次早点来吧~
第44次抽奖，结果为：奖品抽完了，下次早点来吧~
第45次抽奖，结果为：奖品抽完了，下次早点来吧~
第46次抽奖，结果为：奖品抽完了，下次早点来吧~
第47次抽奖，结果为：奖品抽完了，下次早点来吧~
第48次抽奖，结果为：奖品抽完了，下次早点来吧~
第49次抽奖，结果为：奖品抽完了，下次早点来吧~
第50次抽奖，结果为：奖品抽完了，下次早点来吧~
抽奖结束.

Process finished with exit code 0
 */

参考资料

「阅读原文」