数学篇 - 组合,解决赛程规划与自然语言处理(笔记)
组合
组合(combination)是一个数学名词。一般地,从n个不同的元素中,任取m(m≤n)个元素为一组,叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。
对于所有 m 取值的组合之全集合,我们可以叫作全组合(All Combination)。例如对于集合{1, 2, 3}而言,全组合就是{空集, {1}, {2}, {3}, {1, 2}, {1,3} {2, 3}, {1, 2, 3}}。
如何安排世界杯赛程
想让全部的 32 支球队都和其他球队进行一次主客场的比赛.
自己不可能和自己比赛,不可重复的排列中,主场球队有 32 种选择,而客场球队有 31 种选择。那么一共要进行多少场比赛呢?很简单,就是 32x31=992
场!
在实际情况中,赛程设计并没有这样做.
这就是为什么要将所有 32 支队伍分成 8 个小组先进行小组赛的原因。一旦分成小组,每个小组的赛事就是 (4x3)/2=6 场。所有小组赛就是 6x8=48 场。
加上在 16 强阶段开始采取淘汰制,两两淘汰,所以需要 8+4+2+2=16 场淘汰赛(最后一次加 2 是因为还有 3、4 名的决赛),那么整个世界杯决赛阶段就是 48+16=64 场比赛。
这两两配对比赛的场次,我是如何计算出来的?让我引出今天的概念,组合(Combination)。
让计算机来组合队伍
/*
* @Description: 使用函数的递归(嵌套)调用,找出所有可能的队伍组合
* @param teams-目前还剩多少队伍没有参与组合,result-保存当前已经组合的队伍
* @return void
*/
let teams = ["t1", "t2", "t3"];
combine(teams,[],2)
function combine(teams,result,m) {
// 挑选完了m个元素,输出结果
if (result.length == m) {
console.log(result)
return;
}
for (let i = 0; i < teams.length; i++) {
// 从剩下的队伍中,选择一队,加入结果
let newResult = [].concat(result)
newResult.push(teams[i]);
// 只考虑当前选择之后的所有队伍
let rest_teams = teams.slice(i + 1, teams.length)
// 递归调用,对于剩余的队伍继续生成组合
combine(rest_teams, newResult, m);
}
}
有没有发现,这个算法跟上一篇的密码爆破思想非常接近.
利用组合高效处理词组
每篇很长的文章,分隔成一个个的单词,然后对每个单词进行索引,便于日后的查询。但是很多时候,光有单个的单词是不够的,还要考虑多个单词所组成的词组。例如,“red bluetooth mouse”这样的词组。
常见的一种方式是多元文法
。把临近的几个单词合并起来,组合一个新的词组。比如我可以把“red”和“bluetooth”合并为“red bluetooth”,还可以把“bluetooth”和“mouse”合并为“bluetooth mouse”。
如果我们只保留原文的“red bluetooth mouse”,无法将其和用户输入的“bluetooth red mouse”匹配
多个单词出现时,每次用户输入之后将词组排序,例如:
“red bluetooth mouse”,这三个词排序后就是“bluetooth,mouse,red”,而“bluetooth red mouse”排序后也是“bluetooth,mouse,red”,自然两者就能匹配上了。
设计一个抽奖系统
假设现在需要设计一个抽奖系统。需要依次从 100 个人中,抽取三等奖 10 名,二等奖 3 名和一等奖 1 名。请列出所有可能的组合,需要注意的每人最多只能被抽中 1 次。
思路1: 先运行combine(100, 14),对每个结果运行combine(14, 10),再对每个更新的结果运行combine(4, 3)。
思路2 : 从100人中选10人得3等奖,combine(100, 10);再从剩下90人中选3人的3等奖,combine(90, 3);再从剩下87人中选1人得1等奖, combine(87, 1)
这个数值太大,js计算不过来
微信公众号
