# 快速实现随机抽奖程序

查看原文奇舞团博客

一共有 50 个人,从中公平的抽取出 10 个人,而且不重复。

# 直接抽取

TIP

思路:所有人从 1 到 50 依次排号(teamers)。抽几个人就循环几次,每次循环都随机生成一个下标,从原有 teamers 里边取出对应下标的号码,teamers 长度减一

const teamers = Array(50)
    .fill()
    .map((_, i) => i + 1);

// n: 抽取 n 个
function extract(n = 1) {
    let res = [];
    for (let i = 0; i < n; i++) {
        let ind = Math.floor(teamers.length * Math.random());
        res.push(...teamers.splice(ind, 1));
    }
    return res;
}
console.log(extract(10)); // [23, 10, 39, 29, 14, 32, 47, 35, 43, 25]
copy success
Copy successed

问题:

因为每次 splice 一个数字,取 10 个数字需要 splice 10 次,这看起来不是特别好。可以想到另一种方法,先对数组进行“洗牌”,然后一次把 10 个数字取出来:

# 先洗牌

// amount: 总个数; n: 抽取个数
function extract(amount, n = 1) {
    const teamers = Array(50)
        .fill()
        .map((_, i) => i + 1);
    for (let i = amount - 1; i >= 0; i--) {
        let ind = Math.floor((i + 1) * Math.random());
        // 洗牌
        [teamers[ind], teamers[i]] = [teamers[i], teamers[ind]];
    }
    return teamers.slice(0, n);
}
console.log(extract(50, 10)); // [29, 34, 36, 12, 27, 35, 5, 26, 38, 31]
copy success
Copy successed

问题:

上面这个版本也有明显缺点。首先它先把所有的牌都排序了,但实际上只需要排序 10 张牌就好,多余的排序没有必要。其次,它不方便连续抽奖,比如第一次抽取 10 个号,然后再想多抽取 5 个号,它就做不到了。

# 不需要洗所有的牌

function extract(amount, n = 1) {
    const teamers = Array(50)
        .fill()
        .map((_, i) => i + 1);
    for (let i = amount - 1, stop = amount - n - 1; i > stop; i--) {
        let ind = Math.floor((i + 1) * Math.random());
        // 洗牌
        [teamers[ind], teamers[i]] = [teamers[i], teamers[ind]];
    }
    // 获取teamers数组中最后的十个数
    return teamers.slice(-n);
}
console.log(extract(50, 10)); // [29, 34, 36, 12, 27, 35, 5, 26, 38, 31]
copy success
Copy successed

如果取 10 个数,只需要循环 10 次即可,不需要把 50 张牌都洗了。

# 连续抽奖的问题

要解决可以连续抽奖的问题,就需要把 teamers 提取出来(就像方案 1 的随机抽取一样),但是那样的话就使得函数有副作用,虽说是临时写一个抽奖,也不喜欢设计得太糙。或者,那就加一个构造器执行初始化?

function Box(amount) {
    this.teamers = Array(amount)
        .fill()
        .map((_, i) => i + 1);
}
Box.prototype.extract = function(n = 1) {
    let amount = this.teamers.length,
        teamers = this.teamers;

    for (let i = amount - 1, stop = amount - n - 1; i > stop; i--) {
        let ind = Math.floor((i + 1) * Math.random());
        [teamers[ind], teamers[i]] = [teamers[i], teamers[ind]];
    }

    // 获取teamers数组中最后的十个数
    let res = teamers.slice(-n);
    teamers.length = amount - n;

    return res;
};

var box = new Box(50);
var firstPrice = box.extract(10);
var secondPrice = box.extract(5);
console.log(firstPrice, secondPrice); // [2, 27, 46, 44, 19, 14, 16, 49, 26, 17] , [30, 5, 6, 24, 11]
copy success
Copy successed

# 最终版

对于一次可能抽取任意多个获奖人的场景,用 ES6 的 generators 非常合适,我们可以直接拿洗牌的版本略做修改:

function* extract(amount) {
    const teamers = Array(50)
        .fill()
        .map((_, i) => i + 1);

    for (let i = amount - 1; i >= 0; i--) {
        let ind = Math.floor((i + 1) * Math.random());
        // 洗牌
        [teamers[ind], teamers[i]] = [teamers[i], teamers[ind]];

        yield teamers[i];
    }
}

var extractor = extract(50);

// 第一次抽10个人
var firstPrice = Array(10)
    .fill()
    .map(() => extractor.next().value);
// 第二次抽10个人
var secondPrice = Array(10)
    .fill()
    .map(() => extractor.next().value);
// 第三次抽10个人
var thirdPrice = Array(10)
    .fill()
    .map(() => extractor.next().value);
// 第四次抽10个人
var forthPrice = Array(10)
    .fill()
    .map(() => extractor.next().value);
// 第五次抽10个人
var fifthPrice = Array(10)
    .fill()
    .map(() => extractor.next().value);
// 第六次抽10个人
var sixthPrice = Array(5)
    .fill()
    .map(() => extractor.next().value);

console.log(firstPrice); // [25, 14, 17, 41, 45, 18, 33, 42, 5, 48]
console.log(secondPrice); // [10, 23, 4, 29, 35, 50, 7, 26, 34, 28]
console.log(thirdPrice); // [9, 38, 15, 6, 11, 32, 40, 13, 8, 46]
console.log(forthPrice); // [1, 22, 16, 24, 47, 30, 43, 3, 2, 44]
console.log(fifthPrice); // [27, 20, 39, 31, 49, 21, 12, 37, 19, 36]
console.log(sixthPrice); // [undefined, undefined, undefined, undefined, undefined]
copy success
Copy successed

点个Star支持我一下 ~