08丨组合：如何让计算机安排世界杯的赛程？.pdf
25墨值下载
08 | 组合：如何让计算机安排世界杯的赛程？
2018-12-31 黄申
程序员的数学基础课
进入课程
讲述：黄申
时长 12:06 大小 11.09M
你好，我是黄申。
2018 年足球世界杯结束有半年了，当时激烈的赛况你现在还记忆犹新吧？你知道这场足球
盛宴的比赛日程是怎么安排的吗？如果现在你是组委会，你会怎么安排比赛日程呢？我们可
以用上一节的排列思想，让全部的 32 支入围球队都和其他球队进行一次主客场的比赛。
自己不可能和自己比赛，因此在这种不可重复的排列中，主场球队有 32 种选择，而客场球
队有 31 种选择。那么一共要进行多少场比赛呢？很简单，就是 32x31=992 场！这也太夸
张了吧？一天看 2 场，也要 1 年多才能看完！即使球迷开心了，可是每队球员要踢主客场
共 62 场，早已累趴下了。
下载APP
好吧，既然这样，我们是否可以取消主客场制，让任意两个球队之间只要踢 1 场就好啦？
取消主客场，这就意味着原来两队之间的比赛由 2 场降为 1 场，那么所有比赛场次就是
992/2=496 场。还是很多，对吧？
是的，这就是为什么要将所有 32 支队伍分成 8 个小组先进行小组赛的原因。一旦分成小
组，每个小组的赛事就是 (4x3)/2=6 场。所有小组赛就是 6x8=48 场。
再加上在 16 强阶段开始采取淘汰制，两两淘汰，所以需要 8+4+2+2=16 场淘汰赛（最后
一次加 2 是因为还有 3、4 名的决赛），那么整个世界杯决赛阶段就是 48+16=64 场比
赛。
当然，说了这么多，你可能会好奇，这两两配对比赛的场次，我是如何计算出来的？让我引
出今天的概念，组合（Combination）。
组合可以说是排列的兄弟，两者类似但又有所不同，这两者的区别，不知道你还记得不，上
学的时候，老师肯定说过不止一次，那就是，组合是不考虑每个元素出现的顺序的。
从定义上来说，组合是指，从 n 个不同元素中取出 m（1≤m≤n）个不同的元素。例如，
我们前面说到的世界杯足球赛的例子，从 32 支球队里找出任意 2 支球队进行比赛，就是从
32 个元素中取出 2 个元素的组合。如果上一讲中，田忌赛马的规则改一下，改为从 10 匹
马里挑出 3 匹比赛，但是并不关心这 3 匹马的出战顺序，那么也是一个组合的问题。
对于所有 m 取值的组合之全集合，我们可以叫作全组合（All Combination）。例如对于
集合{1, 2, 3}而言，全组合就是{空集, {1}, {2}, {3}, {1, 2}, {1,3} {2, 3}, {1, 2, 3}}。
如果我们安排足球比赛时，不考虑主客场，也就是不考虑这两只球队的顺序，两队只要踢一
次就行了。那么从 n 个元素取出 m 个的组合，有多少种可能呢？
我们假设某种运动需要 3 支球队一起比赛，那么 32 支球队就有 32x31x30 种排列，如果
三支球队在一起只要比一场，那么我们要抹除多余的比赛。三支球队按照任意顺序的比赛有
3x2x1=6 场，所以从 32 支队伍里取出 3 支队伍的组合是 (32x31x30)/(3x2x1)。基于此，
我们可以扩展成以下两种情况。
n 个元素里取出 m 个的组合，可能性数量就是 n 个里取 m 个的排列数量，除以 m 个全
排列的数量，也就是 (n! / (n-m)!) / m!。
of 14
25墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论