掘金活动抽奖老不中？快来和我一起“优化”抽奖算法吧

前言

掘金经常在沸点搞一些抽奖活动，身为中奖绝缘体的我每次都是当分母，我一度怀疑是抽奖算法“有问题”，review了它的抽奖算法之后，我决定给他做一次“改良”。

它的抽奖算法有两个版本，核心都是JS随机数。

站长直播时的抽奖算法(简陋版)

我们都知道掘金的用户名是不会重复的，所以可以用用户名来抽奖：获取所有参与用户的用户名 -> 将用户名放进数组 -> 数组去重 -> 生成0到数组长度范围内的随机数 -> 利用数组索引找到用户名。

这样做的缺点很明显，一个用户可能中奖两次，需要再抽一次。

沸点活动的新抽奖算法

核心代码如下，去重后的用户先随机乱序，再取前N名。

users.slice().sort(() => Math.random() - 0.5).slice(0, count)

旧算法的缺陷

随机数是否公平？答案是肯定的，当你生成的次数足够多，每个数出现的概率是一样的。但是目前我们的生成次数有限，随机数就不再是公平的。

那么如何让每个人都雨露均沾呢？即在有限次生成随机数的情况下中奖概率接近相同。

算法改良1

我先来尝试下修改第一种抽奖算法。

位数相同

想要每个随机数生成的概率接近，首先要让所有人都在同一起点，即每个人编号的位数是相同的。

假设参与人数是0-89，则让每个人的编号都加上10。如果50人参加，即生成10-60的随机数

假设参与人数是90-899，则让每个人的编号都加上100。如果500人参加，即生成100-600的随机数。

假设参与人数是900-8999，则让每个人的编号都加上1000。如果5000人参加，即生成1000-6000的随机数。

以此类推，在不改变所有人编号位数的前提下，所有人的编号都加上最小的N位数

增加随机次数

按照上面的算法，如果500人参加，直接生成100-600的随机数也不太好，边界数字生成的概率还是比中间数小。我们可以按个位、十位、百位、千位分开生成，然后再拼成一起。

假设参与人数是511，那么生成的随机数范围是100-611。

首先生成百位数，范围是1-6。

再生成十位数0-9，个位数0-9。

生成之后需要校验一下，数字是否存在。

比如说分别生成了6、2、0，620是不存在的，继续生成。

优化用户的序号

用户序号以用户最后一次回复为准，比如某个用户回复了两次，序号分别是 2 和 20，由于我们会做去重操作，所以这个用户的序号就是 2，但是实际上用户肯定希望以最后一次回复为准，那应该如何处理呢，办法也很简单。数组先倒序，去重再倒序回来即可。

talk is cheap show me the code

const lotteryDraw = () => {
  const luckUserNum = Number(window.prompt('你想抽几位锦鲤?')); // 中奖人数
  const userArr = new Array(300).fill(1).map((item,index) => index); // 模拟参与人数
  const length = userArr.length;
  let add = 0;
  let times = 1;
  if(length<89){
    add = 10;
    times = 2;
  }else if(length < 899){
    add = 100;
    times = 3;
  }else if(length < 8999){
    add = 1000;
    times = 4;
  }else{
    add = 10000;
    times = 5;
  }

  const min = add;
  const max = add + length;
  const luckUser = [];

  const creatNumber = times => {
    let num = '';
    for(let i = 0; i < times; i++){
      const temNum = Math.floor( Math.random ( ) * 10);
      num += temNum;
    }
    return +num;
  }

  while (luckUser.length < luckUserNum) {
    const userIndex = creatNumber(times);
    if(userIndex < max && userIndex >= min && !luckUser.includes(userIndex)){
      luckUser.push(userIndex-add)
    }
  }

  console.log(luckUser);
}

lotteryDraw();

算法改良2

第2种抽奖算法可以改进的点在于数组截取的起点不要为0，先随机生成一个范围为 [ 0, 数组长度 - 中奖人数 ] 的随机数，以这个数为起点截取数组就好了。

总结

数学渣渣只能尽力保证抽奖公平，希望下次中奖有我！！！