java版抽奖算法

川长思鸟来 2022-12-08 12:56 199阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9kZWhvbmc_size_16_color_FFFFFF_t_70][]

奖品大致有12种，根据需求来说苹果11Pro和华为P40的概率为0，所以只有10种奖品，我们的奖池里面只有10种奖品。

<table style="width:345.77pt;"> 
 <tbody> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;width:54pt;">奖品名称</td> 
 <td style="border-color:#000000;vertical-align:middle;width:54pt;">奖品类型</td> 
 <td style="border-color:#000000;vertical-align:middle;width:237.75pt;">奖品中将概率%</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">100元现金红包</td> 
 <td style="border-color:#000000;vertical-align:middle;">实物</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">0.1</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">100元京东充值卡</td> 
 <td style="border-color:#000000;vertical-align:middle;">实物</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">0.4</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">50元话费</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">1</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">永久翻译包</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">3</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">7天翻译包</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">5</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">230颗蓝钻</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">5</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">1个月会员</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">8</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">100粉钻</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">10</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">20粉钻</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">20</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:middle;">5粉钻</td> 
 <td style="border-color:#000000;vertical-align:middle;">虚拟物品</td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;">47.5</td> 
 </tr> 
 </tbody> 
</table>

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9kZWhvbmc_size_16_color_FFFFFF_t_70 1][]

我们根据概率依次从小到大排列。这样的话就比较简单了，我们生成一个列表，分成几个区间，例如列表长度100，0-0.1是红包的区间,0.2-0.5是充值卡的区间,0.5到1.5是话费的重置区间，然后随机从100取出一个数，看落在哪个区间。算法时间复杂度：预处理O(MN)，随机数生成O(1)，空间复杂度O(MN)，其中N代表物品种类，M则由最低概率决定。

public class LottoRsa {
 	private static final List<Prize> prizePool=new ArrayList<Prize>() {
 		{
 			this.add(new Prize("100元现金"));
 			this.add(new Prize("100元京东卡"));
 			this.add(new Prize("50元话费"));
 			this.add(new Prize("永久翻译包"));
 			this.add(new Prize("7天翻译包"));
 			this.add(new Prize("230颗蓝砖"));
 			this.add(new Prize("1个月会员"));
 			this.add(new Prize("100粉砖"));
 			this.add(new Prize("20粉砖"));
 			this.add(new Prize("5粉砖"));
 		}
 	};
 	
 	public static Prize getPrize() {
 		int randomInt=RandomUtil.randomInt(100);
 		int randomFloat=RandomUtil.randomInt(10);
 		
 		Float probability=Float.valueOf(randomInt+"."+randomFloat);
 		
 		if(probability>=0&&probability<=0.1) {
 			return prizePool.get(0);
 		}
 		if(probability>=0.1&&probability<=0.5) {
 			return prizePool.get(1);
 		}
 		if(probability>=0.5&&probability<=1.5) {
 			return prizePool.get(2);
 		}
 		if(probability>=1.5&&probability<=4.5) {
 			return prizePool.get(3);
 		}
 		if(probability>=4.5&&probability<=9.5) {
 			return prizePool.get(4);
 		}
 		if(probability>=9.5&&probability<=14.5) {
 			return prizePool.get(5);
 		}
 		if(probability>=14.5&&probability<=22.5) {
 			return prizePool.get(6);
 		}
 		if(probability>=22.5&&probability<=32.5) {
 			return prizePool.get(7);
 		}
 		if(probability>=32.5&&probability<=52.5) {
 			return prizePool.get(8);
 		}
 		return prizePool.get(9);
 	}
 	public static void main(String[] args) {
 		for(int i=0;i<100;i++) {
 		System.out.println(getPrize());
 		}
 	}
 }

第二种就是一般的离散算法，通过概率分布构造几个点，\[10, 30, 60, 100\]，没错，后面的值就是前面依次累加的概率之和（是不是像斐波那契数列）。在生成1~100的随机数，看它落在哪个区间，比如50在\[30,60\]之间，就是类型3。在查找时，可以采用线性查找，或效率更高的二分查找，时间复杂度O(logN)。

两个概念，PDF（密度分布函数）和 CDF（累积分布函数）两种概率分布，分别对应如上两种算法：

譬如说如上的PDF\[0.1,0.2,0.3,0.4\]，将每种概率当做一列，别名算法最终的结果是要构造拼装出一个每一列合都为1的矩形，若每一列最后都要为1，那么要将所有元素都乘以4（概率类型的数量）

![Center][]

此时会有概率大于1的和小于1的，接下来就是构造出某种算法用大于1的补足小于1的，使每种概率最后都为1，注意，这里要遵循一个限制：每列至多是两种概率的组合。

![Center 1][]

最终，我们得到了两个数组，一个是在下面原始的prob数组\[0.4,0.8,0.6,1\]，另外就是在上面补充的Alias数组，其值代表填充的那一列的序号索引，（如果这一列上不需填充，那么就是NULL），\[3,4,4,NULL\]。当然，最终的结果可能不止一种，你也可能得到其他结果。

等等，这个问题还没有解决，得到这两个数组之后，随机取其中的一列，比如是第三列，让prob\[3\]的值与一个随机小数f比较，如果f小于prob\[3\]，那么结果就是3，否则就是Alias\[3\]，即4。

我们可以来简单验证得到的概率是不是正确的，比如随机到第三列的概率是1/4，得到第三列下半部分的概率为1/4\*3/5，记得在第一列还有它的一部分，那里的概率为1/4\*(1-2/5)，两者相加最终的结果还是3/10，符合原来的pdf概率。这种算法初始化较复杂，但生成随机结果的时间复杂度为O(1)，是一种性能非常好的算法。

<table> 
 <tbody> 
 <tr> 
 <td>T</td> 
 <td>1</td> 
 <td>2</td> 
 <td>3</td> 
 <td>4</td> 
 </tr> 
 <tr> 
 <td>PDF</td> 
 <td>0.1</td> 
 <td>0.2</td> 
 <td>0.3</td> 
 <td>0.4</td> 
 </tr> 
 <tr> 
 <td>Alias</td> 
 <td>3</td> 
 <td>4</td> 
 <td>4</td> 
 <td>NULL</td> 
 </tr> 
 </tbody> 
</table>

public final class AliasMethod {
 /* The random number generator used to sample from the distribution. */
 private final Random random;
 
 /* The probability and alias tables. */
 private final int[] alias;
 private final double[] probability;
 
 /**
 * Constructs a new AliasMethod to sample from a discrete distribution and
 * hand back outcomes based on the probability distribution.
 * 
 * Given as input a list of probabilities corresponding to outcomes 0, 1,
 * ..., n - 1, this constructor creates the probability and alias tables
 * needed to efficiently sample from this distribution.
 *
 * @param probabilities The list of probabilities.
 */
 public AliasMethod(List<Double> probabilities) {
 this(probabilities, new Random());
 }
 
 /**
 * Constructs a new AliasMethod to sample from a discrete distribution and
 * hand back outcomes based on the probability distribution.
 * 
 * Given as input a list of probabilities corresponding to outcomes 0, 1,
 * ..., n - 1, along with the random number generator that should be used
 * as the underlying generator, this constructor creates the probability
 * and alias tables needed to efficiently sample from this distribution.
 *
 * @param probabilities The list of probabilities.
 * @param random The random number generator
 */
 public AliasMethod(List<Double> probabilities, Random random) {
 /* Begin by doing basic structural checks on the inputs. */
 if (probabilities == null || random == null)
 throw new NullPointerException();
 if (probabilities.size() == 0)
 throw new IllegalArgumentException("Probability vector must be nonempty.");
 
 /* Allocate space for the probability and alias tables. */
 probability = new double[probabilities.size()];
 alias = new int[probabilities.size()];
 
 /* Store the underlying generator. */
 this.random = random;
 
 /* Compute the average probability and cache it for later use. */
 final double average = 1.0 / probabilities.size();
 
 /* Make a copy of the probabilities list, since we will be making
 * changes to it.
 */
 probabilities = new ArrayList<Double>(probabilities);
 
 /* Create two stacks to act as worklists as we populate the tables. */
 Deque<Integer> small = new ArrayDeque<Integer>();
 Deque<Integer> large = new ArrayDeque<Integer>();
 
 /* Populate the stacks with the input probabilities. */
 for (int i = 0; i < probabilities.size(); ++i) {
 /* If the probability is below the average probability, then we add
 * it to the small list; otherwise we add it to the large list.
 */
 if (probabilities.get(i) >= average)
 large.add(i);
 else
 small.add(i);
 }
 
 /* As a note: in the mathematical specification of the algorithm, we
 * will always exhaust the small list before the big list. However,
 * due to floating point inaccuracies, this is not necessarily true.
 * Consequently, this inner loop (which tries to pair small and large
 * elements) will have to check that both lists aren't empty.
 */
 while (!small.isEmpty() && !large.isEmpty()) {
 /* Get the index of the small and the large probabilities. */
 int less = small.removeLast();
 int more = large.removeLast();
 
 /* These probabilities have not yet been scaled up to be such that
 * 1/n is given weight 1.0. We do this here instead.
 */
 probability[less] = probabilities.get(less) * probabilities.size();
 alias[less] = more;
 
 /* Decrease the probability of the larger one by the appropriate
 * amount.
 */
 probabilities.set(more,
 (probabilities.get(more) + probabilities.get(less)) - average);
 
 /* If the new probability is less than the average, add it into the
 * small list; otherwise add it to the large list.
 */
 if (probabilities.get(more) >= 1.0 / probabilities.size())
 large.add(more);
 else
 small.add(more);
 }
 
 /* At this point, everything is in one list, which means that the
 * remaining probabilities should all be 1/n. Based on this, set them
 * appropriately. Due to numerical issues, we can't be sure which
 * stack will hold the entries, so we empty both.
 */
 while (!small.isEmpty())
 probability[small.removeLast()] = 1.0;
 while (!large.isEmpty())
 probability[large.removeLast()] = 1.0;
 }
 
 /**
 * Samples a value from the underlying distribution.
 *
 * @return A random value sampled from the underlying distribution.
 */
 public int next() {
 /* Generate a fair die roll to determine which column to inspect. */
 int column = random.nextInt(probability.length);
 
 /* Generate a biased coin toss to determine which option to pick. */
 boolean coinToss = random.nextDouble() < probability[column];
 
 /* Based on the outcome, return either the column or its alias. */
 /* Log.i("1234","column="+column);
 Log.i("1234","coinToss="+coinToss);
 Log.i("1234","alias[column]="+coinToss);*/
 return coinToss ? column : alias[column];
 }
 
 public static void main(String[] args) {
 TreeMap<String, Double> map = new TreeMap<String, Double>();
 map.put("苹果11pro 256G", 0.0);
 map.put("华为P40 pro", 0.0);
 map.put("100元现金", 0.001);
 map.put("100元京东卡", 0.004);
 map.put("50元话费", 0.01);
 map.put("永久翻译包",0.03);
 map.put("7天翻译包", 0.05);
 map.put("230颗蓝砖", 0.05);
 map.put("一个月会员", 0.08);
 map.put("100粉砖", 0.1);
 map.put("20粉砖",0.2);
 map.put("5粉砖",0.475);
 List<Double> list = new ArrayList<Double>(map.values());
 List<String> gifts = new ArrayList<String>(map.keySet());
 
 AliasMethod method = new AliasMethod(list);
 
 Map<String, AtomicInteger> resultMap = new HashMap<String, AtomicInteger>();
 
 for (int i = 0; i < 100000; i++) {
 int index = method.next();
 String key = gifts.get(index);
 if (!resultMap.containsKey(key)) {
 resultMap.put(key, new AtomicInteger());
 }
 resultMap.get(key).incrementAndGet();
 }
 for (String key : resultMap.keySet()) {
 System.out.println(key + "==" + resultMap.get(key));
 }
 
 }
 }

最后输出结果为100元京东卡==402  
5粉砖==47440  
一个月会员==7984  
100元现金==111  
230颗蓝砖==4988  
100粉砖==10075  
50元话费==952  
永久翻译包==2980  
20粉砖==20089  
7天翻译包==4979

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9kZWhvbmc_size_16_color_FFFFFF_t_70]: /images/20221123/ff77315e8c0445cd83edfa1b562a8c32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9kZWhvbmc_size_16_color_FFFFFF_t_70 1]: /images/20221123/3720c73d24844b32bedc865652318b68.png
[Center]: /images/20221123/9a623a2712974b1a9a3134214b0a0f66.png
[Center 1]: /images/20221123/f6a418cd5f1f49408792b55b9e4cc889.png