 23478 人已学习

0/4登录后，你可以任选4讲全文学习。

01 | 二进制：不了解计算机的源头，你学什么编程
02 | 余数：原来取余操作本身就是个哈希函数
03 | 迭代法：不用编程语言的自带函数，你会如何计算平方根？
04 | 数学归纳法：如何用数学归纳提升代码的运行效率？
05 | 递归（上）：泛化数学归纳，如何将复杂问题简单化？
06 | 递归（下）：分而治之，从归并排序到MapReduce
07 | 排列：如何让计算机学会“田忌赛马”？
08 | 组合：如何让计算机安排世界杯的赛程？
09 | 动态规划（上）：如何实现基于编辑距离的查询推荐？
10 | 动态规划（下）：如何求得状态转移方程并进行编程实现？
11 | 树的深度优先搜索（上）：如何才能高效率地查字典？
12 | 树的深度优先搜索（下）：如何才能高效率地查字典？
13 | 树的广度优先搜索（上）：人际关系的六度理论是真的吗？
14 | 树的广度优先搜索（下）：为什么双向广度优先搜索的效率更高？
15 | 从树到图：如何让计算机学会看地图？
16 | 时间和空间复杂度（上）：优化性能是否只是“纸上谈兵”？
17 | 时间和空间复杂度（下）：如何使用六个法则进行复杂度分析？
18 | 总结课：数据结构、编程语句和基础算法体现了哪些数学思想？

19 | 概率和统计：编程为什么需要概率和统计？
20 | 概率基础（上）：一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础（下）：联合概率、条件概率和贝叶斯法则，这些概率公式究竟能做什么？
22 | 朴素贝叶斯：如何让计算机学会自动分类？
23 | 文本分类：如何区分特定类型的新闻？
24 | 语言模型：如何使用链式法则和马尔科夫假设简化概率模型？
25 | 马尔科夫模型：从PageRank到语音识别，背后是什么模型在支撑？
26 | 信息熵：如何通过几个问题，测出你对应的武侠人物？
27 | 决策树：信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方：如何寻找关键特征？
29 | 归一化和标准化：各种特征如何综合才是最合理的？
30 | 统计意义（上）：如何通过显著性检验，判断你的A/B测试结果是不是巧合？
31 | 统计意义（下）：如何通过显著性检验，判断你的A/B测试结果是不是巧合？
32 | 概率统计篇答疑和总结：为什么会有欠拟合和过拟合？

33 | 线性代数：线性代数到底都讲了些什么？
34 | 向量空间模型：如何让计算机理解现实事物之间的关系？
35 | 文本检索：如何让计算机处理自然语言？
36 | 文本聚类：如何过滤冗余的新闻？
37 | 矩阵（上）：如何使用矩阵操作进行PageRank计算？
38 | 矩阵（下）：如何使用矩阵操作进行协同过滤推荐？
39 | 线性回归（上）：如何使用高斯消元求解线性方程组？
40 | 线性回归（中）：如何使用最小二乘法进行直线拟合？
41 | 线性回归（下）：如何使用最小二乘法进行效果验证？
42 | PCA主成分分析（上）：如何利用协方差矩阵来降维？
43 | PCA主成分分析（下）：为什么要计算协方差矩阵的特征值和特征向量？
44 | 奇异值分解：如何挖掘潜在的语义关系？
45 | 线性代数篇答疑和总结：矩阵乘法的几何意义是什么？

46 | 缓存系统：如何通过哈希表和队列实现高效访问？
47 | 搜索引擎（上）：如何通过倒排索引和向量空间模型，打造一个简单的搜索引擎？
48 | 搜索引擎（下）：如何通过查询的分类，让电商平台的搜索结果更相关？
49 | 推荐系统（上）：如何实现基于相似度的协同过滤？
50 | 推荐系统（下）：如何通过SVD分析用户和物品的矩阵？
51 | 综合应用篇答疑和总结：如何进行个性化用户画像的设计？

# 08 | 组合：如何让计算机安排世界杯的赛程？ 2018 年足球世界杯结束有半年了，当时激烈的赛况你现在还记忆犹新吧？你知道这场足球盛宴的比赛日程是怎么安排的吗？如果现在你是组委会，你会怎么安排比赛日程呢？我们可以用上一节的排列思想，让全部的 32 支入围球队都和其他球队进行一次主客场的比赛。

0/1000字 ## 精选留言(29)

• 风轨
从100人中选10人得3等奖，C(100, 10) = 17310309456440
再从剩下90人中选3人的3等奖，C(90, 3) = 117480
再从剩下87人中选1人得1等奖， C(87, 1) = 87
总共有大约有1.8×10^20种可能性，
假设我们的计算机每1ns就能输出1个结果，全部输出来大约要5610年！
假设每个结果占13个字节，把结果保存下来大约要占1995EB，远远大于世界上存储总容量！

当数据量比较小时，还是可以算的：
public class Combination {

/**
* 求组合数
*
* @param n
* @param r
* @return
*/
static int c(int n, int r) {
if (r > n) {
return 0;
}
int R = n - r;
int ret = 1;
while (n > R) {
ret *= n--;
}
while (r > 1) {
ret /= r--;
}
return ret;
}

/**
* 求组合情况
* @param es
* @param r
* @param I 数组es开始取数位置
* @return
*/
static int[][] C(int[] es, int r, int I) {
int[][] rst = new int[c(es.length - I, r)][];
if (r == 1) {
for (int rsti = 0; rsti < rst.length; rsti++, I++) {
rst[rsti] = new int[] { es[I] };
}
} else {
for (int rsti = 0; I < es.length; I++) {
int[][] srst = C(es, r - 1, I + 1);
for (int[] sc : srst) {
int[] t = rst[rsti] = new int[sc.length + 1];
t = es[I];
System.arraycopy(sc, 0, t, 1, sc.length);
rsti++;
}
}
}
return rst;
}

public static void main(String[] args) {
int[][] c = C(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 3, 0);
for (int[] cc : c) {
System.out.println(Arrays.toString(cc));
}
/**
* 输出结果
* [1, 2, 3]
* [1, 2, 4]
* [1, 2, 5]
* [1, 2, 6]
* ··· 省略111行 ···
* [6, 9, 10]
* [7, 8, 9]
* [7, 8, 10]
* [7, 9, 10]
* [8, 9, 10]
*
*/
}
}

作者回复: 确实数字取得太大了

2018-12-31
1
9
• 行者
案例python实现：

comb = ['t1', 't2', 't3', 't4', 't5']
import copy

def combination(n, comb, result):

if n == 0:
print(result)
return
for i in comb:
newResult = copy.copy(result)
newComb = copy.copy(comb)
newResult.append(i)
newComb = list(set(newComb).difference(set(comb[:comb.index(i) + 1])))
combination(n - 1, newComb, newResult)

combination(4, comb, [])
2019-01-02
5
• Wing·三金
思路一：
先运行combine(100, 1)，将所有结果保存。然后用一层迭代对每个结果运行combine(99, 3)，将所有结果append进去。
然后再来一层迭代对上一结果运行combine(96, 10)，同样依次append进去。
此处的关键点在于每个迭代下得将上一结果中的数拿掉，以及得保存临时结果。

此思路也等价于直接上三个嵌套循环+运行递归程序。

思路二：
先运行combine(100, 14)，对每个结果运行combine(14, 10)，再对每个更新的结果运行combine(4, 3)。其实就是思路一逆过来。

理论上二者的复杂度是一样的，用scipy验证了下确实如此。
2018-12-31
5
• Ricky
#include <iostream>
#include <vector>

using namespace std;
void winPrize(int f, int s, int t,
vector<int> &first, vector<int> &second, vector<int> &third, vector<int> &base) {

if (first.size() == f && second.size() == s && third.size() == t) {
cout << "\nAwards Notification" << endl;
cout << "Prize 1: " << first.back() << endl;
cout << "Prize 2: ";
for (int x: second) {
cout << x << " ";
}
cout << endl;
cout << "Prize 3: ";
for (int y: third) {
cout << y << " ";
}
cout << endl;
return;
}
for (int x: base) {
// 每次仅添加一个成员进奖项圈, 优先级按照一等奖 > 二等奖 > 三等奖
auto f1 = first, s1 = second, t1 = third, left = base;
if (first.size() < f) {
f1.push_back(x);
} else if (second.size() < s) {
s1.push_back(x);
} else if (third.size() < t) {
t1.push_back(x);
}
// 删除成员
auto iter = left.begin();
while (iter != left.end()) {
if (*iter == x) {
iter = left.erase(iter);
} else iter++;
}
winPrize(f, s, t, f1, s1, t1, left);
}
}

void winPrize(int tl, int f, int s, int t) {
vector<int> first, second, third, base;
for (int i = 0; i < tl; ++i) {
base.push_back(i);
}

winPrize(f, s, t, first, second, third, base);
}
int main() {
cout << "Prize Result" << endl;
winPrize(10, 1, 2, 3);
return 0;
}
******************结果********************
Prize 1: 2
Prize 2: 0 6
Prize 3: 8 3 1

Prize 1: 2
Prize 2: 0 6
Prize 3: 8 3 4

Prize 1: 2
Prize 2: 0 6
Prize 3: 8 3 5

Prize 1: 2
Prize 2: 0 6
Prize 3: 8 3 7
2019-01-10
4
• qinggeouye
python (比较粗暴的解法...)
import copy

def lucky_draw_combination(n, m, result=None, all_results=None):
"""
使用函数的递归（嵌套）调用，找出所有可能的中奖者的组合
:param all_results: 中奖者的所有组合
:param n: 参与抽奖的人
:param result: 抽奖结果
:param m: 中奖的人数
:return: None
"""
if result is None:
result = []
if all_results is None:
all_results = []
if len(result) == m:
# print(result)
return all_results.append(result)
for i in range(len(n)):
# 从剩下的人中，抽出一个人加入结果
new_result = copy.copy(result)
new_result.append(n[i])
# 每人最多只能被抽中一次，当前被抽中的人之后的人，进入下一次抽奖
rest_n = n[i + 1: len(n)]
# 递归调用 在剩下的人中继续抽奖
lucky_draw_combination(rest_n, m, new_result, all_results)
return all_results

if __name__ == "__main__":
total = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 被抽奖人列表
m_ = [3, 2, 1] # 三等奖、二等奖、一等奖的个数
lucky1 = lucky_draw_combination(total, m_)
for k1 in lucky1:
total2 = copy.copy(total)
for j1 in k1:
total2.remove(j1)
lucky2 = lucky_draw_combination(total2, m_)
for k2 in lucky2:
total3 = copy.copy(total2)
for j2 in k2:
total3.remove(j2)
lucky3 = lucky_draw_combination(total3, m_)
for k3 in lucky3:
print(k1, k2, k3)
2019-02-10
3
• Paul Shan
总结
排列的递归公式是P(n,m) = nP(n-1,m-1)
可以按照这条公式组织递归，也就是一次n的循环（放入第i号元素）调用P(n-1,m-1)

组合的递归公式是C(n,m) = C(n-1,m-1) +C(n-1,m)
可以按照这条公式（放入或者不放入第0号元素）递归调用
2019-08-21
1
• flow
// JavaScript实现
var arr = [1, 2, 3, 4, 5, 6];

function genGroup(arr, result, count) {
if (result.length === count) {
console.log(result);
return;
}

for (let i = 0; i < arr.length; i++) {
let new_arr = [...arr];
let new_result = [...result];
new_result.push(arr[i]);
new_arr.splice(0, i + 1);
genGroup(new_arr, new_result, count);
}
}

genGroup(arr, [], 3);
// 思考题也是同理, 100人取14个, 第1个为一等奖, 2-4为二等奖, 5-14为三等奖
2019-04-16
1
• 夏微凉
黄老师，我这几天一直在纠结思考题，总共10人，一等名1名，二等奖2名，三等3名，还是没有完全理解思路，希望老师方便的时候解答下

作者回复: 这道题是用到了组合及排列，先看100个人里取1人的数量是C100,1 (格式问题，C100,1表示从100人里取1人的组合数量)，剩下99人里取2人为C99,2，再剩下97人里取3人为C97,3，然后再利用排列，总共可能为C100,1 x C99,2 x C97,3

2019-01-14
1
• 文刂 氵共 超
使用C++实现组合问题-从n个数中取出m个不同的元素，不考虑顺序

#include <iostream>
#include <vector>

using namespace std;

template <class T>
void PrintVector(vector<T> & DataVec)
{
for (size_t i = 0; i < DataVec.size(); ++i)
{
cout << DataVec[i] << " ";
}
cout << endl;
}

template <class T>
void Combination(vector<T> &DataVec, int m, vector<T> &resultVec)
{
if (m <= 0 && m > DataVec.size())
{
return;
}

if (resultVec.size() == m)
{
PrintVector(resultVec);
return;
}

for (size_t i = 0; i < DataVec.size(); ++i)
{
vector<T> tempResultVec = resultVec;
tempResultVec.push_back(DataVec[i]);

vector<T> tempDataVec(DataVec.begin()+i+1, DataVec.end());

Combination(tempDataVec, m, tempResultVec);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
vector<int> resultV;
int dataList[] = {2,6,8,23,78,45,32,64};
vector<int> dataV(dataList, dataList+8);

Combination(dataV, 5, resultV);

PrintVector(resultV);

return 0;
}

作者回复: 使用栈来实现递归过程的想法很棒

2019-01-04
1
• Youngggg
由于数量过大 设置10个人中 1等奖1名 2等奖2名 3等奖3名
import copy
word = []
for i in range(1,11):
word.append(i)
def sort(one_num, two_num, three_num, one_result=[], two_result=[], three_result=[]):
if len(one_result) == one_num and len(two_result) == two_num and len(three_result) == three_num:
print("一等奖", one_result)
print("二等奖", two_result)
print("三等奖", three_result)
return
else:
i = 0
while i < len(word):
if word[i] not in one_result and len(one_result) < one_num:
if len(one_result)>0:
if one_result[-1] > word[i]:
i = i+1
continue
new_one_result = copy.copy(one_result)
new_one_result.append(word[i])
i = i+1
sort(one_num, two_num, three_num, new_one_result, [], [])
elif word[i] not in one_result and word[i] not in two_result and len(two_result) < two_num:
if len(two_result)>0:
if two_result[-1] > word[i]:
i = i + 1
continue
new_two_result = copy.copy(two_result)
new_two_result.append(word[i])
i = i+1
sort(one_num, two_num, three_num, one_result, new_two_result, [])
elif word[i] not in one_result and word[i] not in two_result and word[i] not in three_result and len(three_result) < three_num:
if len(three_result)>0:
if three_result[-1] > word[i]:
i = i+1
continue
new_three_result = copy.copy(three_result)
new_three_result.append(word[i])
i = i+1
sort(one_num, two_num, three_num, one_result, two_result, new_three_result)
else:
i = i+1
continue
sort(1, 2, 3, [], [], [])
运行结果：
一等奖 
二等奖 [2, 3]
三等奖 [4, 5, 6]
.....
2019-01-02
1
• teddytyy
100！/（90！*10！） * 90！/（87！*3！） * 87
2019-12-05
• aoe
原来组合这么强大！
2019-11-30
• 顾骨
// decrease decreate []int{3,2,1} to []int{0,0,0} gradually
func decrease(c []int) {
for i := range c {
if 0 != c[i] {
c[i]--
break
}
}
}

// delElement delete target element from c
func delElement(c []string, target string) []string {
var newc []string
for i := range c {
if target == c[i] {
newc = append(newc, c[0:i]...)
newc = append(newc, c[i+1:]...)
return newc
}
}
return nil
}

// in a total of 10 person, the number of third prize is 3,
// the number of second prize is 2,the number of first prize is 1,
// combinations=120*21*5=12600
//
// prize format: int[3,2,1], it means the number of third prize is 3,the number of second prize is 2,the number of first prize is 1
func lottery(origin, rest, result []string, prize []int) {
// it means that the third prize is over, go to the second prize and so on
if 0 == prize {
origin = rest
prize = prize[1:]
}

// it means lottery game is over, print result
if 0 == len(prize) {
fmt.Println(result)
return
}

for i := range origin {
var newResult []string
newResult = append(newResult, result...) // copy result
newResult = append(newResult, origin[i])

var newRest []string
newRest = delElement(rest, origin[i])

var newPrize []int
newPrize = append(newPrize, prize...)
decrease(newPrize)

lottery(origin[i+1:], newRest, newResult, newPrize)
}
}

func main() {
in := []string{"m0", "m1", "m2", "m3", "m4"}
lottery(in, in, []string{}, []int{2, 1, 1}) //output: 60
fmt.Println("-------------------------")
in = []string{"m0", "m1", "m2", "m3", "m4", "m5", "m6", "m6", "m8", "m9"}
lottery(in, in, []string{}, []int{3, 2, 1}) //output: 12600
}
2019-11-15
• 建强
简单地用Python写了一程序，由于组合的数量太多，程序中加了适当的限制
import copy
'''
参数说明：
all_person： 全体人员列表
sel_person: 可选人员列表
award_rank: 当前正在抽奖的等级
award_result： 各奖项的人员列表
award_psn_num：各奖项的人数列表
'''
def assemble(all_person,sel_person,award_rank,award_result,award_psn_num):
global schema_num
global schema_limit

#超出组合限制，则不再作组合运算
if schema_limit > 0 and schema_num > schema_limit:
return

#输出结果
if sum(award_psn_num) == 0:
schema_num += 1
print('-'*10,'方案'+ str(schema_num), '-'*10)
for i in range(len(award_result)):
print('{}等奖：{}'.format(i+1,','.join(award_result[i])))
print('-'*30)
print()
return

#挑选当前奖项的人员
i = award_rank - 1

if i>= 0 and award_psn_num[i] > 0:
new_award_psn_num = award_psn_num.copy()
new_award_psn_num[i] -= 1
for j in range(len(sel_person)):
new_award_result = copy.deepcopy(award_result)
new_award_result[i].append(sel_person[j])
new_sel_person = sel_person[j+1:].copy()
assemble(all_person, new_sel_person, award_rank, new_award_result, new_award_psn_num)
else:
#初始化下一奖项的可选人员
if i > 0 and len(award_result[i-1]) == 0:
new_sel_person = all_person.copy()

award_psn = []
for result in award_result:
award_psn += result

for psn in award_psn:
new_sel_person.remove(psn)

#抽取下一奖项人员
assemble(all_person, new_sel_person, award_rank-1, award_result, award_psn_num)

def main():
person_num = 100 #总人数
award3_num = 10 #三等奖人数
award2_num = 3 #二等奖人数
award1_num = 1 #一等奖人数
person_list = ['P' + str(i) for i in range(person_num)]
assemble(person_list, person_list.copy(), 3, [[], [], []], [award1_num, award2_num, award3_num])

if __name__ == '__main__':
schema_num = 0
schema_limit = 10 #限制组合的次数
main()
2019-10-27
• monalisali
老师那个 “red bluetooth mouse” 真是大开眼界了！ 其实把数学思维对应到程序解决方案这个过程才是最难的，就像程序员要把现实世界的问题抽象成代码一样。

作者回复: 很高兴对你有所帮助！

2019-10-23
• 丁丁历险记
讲个段子
淘汰赛 14只球队输一场，第四名输两场。
刚好16场。
2019-10-09
• Paul Shan
思考题
C(100,14) C(14,10)C(4,3)种可能性
2019-08-20
• C语言 递归实现组合

#include <stdio.h>

//记录项的定义
typedef struct record_type {
int data;
} RecordType;

#define MAX_NBR 100

static void visit(RecordType r[], int s[], int n)
{
int i;

for (i = 0; i < n - 1; i++)
printf("%d, ", r[s[i]].data);
printf("%d\n", r[s[i]].data);
}

// s 和 rest 数组，存的是索引
void recursion(RecordType r[], int s[], int n, int rest[], int m, int num)
{
if (n < num)
{
int i, j;
int rest2[MAX_NBR];

for (i = 0; i < m; i++)
{
s[n] = rest[i];
for (j = 0; j < m-i-1; j++)
rest2[j] = rest[i+1+j];

recursion(r, s, n + 1, rest2, m-i-1, num);
}
}
else
{
visit(r, s, n);
}
}

void combination(RecordType r[], int len, int num)
{
int n, m;
int s[MAX_NBR], rest[MAX_NBR];

n = 0;
m = len;
for (int i = 0; i < len; i++)
rest[i] = i;

recursion(r, s, n, rest, m, num);
}

int main(void)
{
int data = { 1, 2, 3, 4, 5 };
RecordType r;

for (int i = 0; i < 5; i++)
r[i].data = data[i];

combination(r, 5, 3);
}
2019-06-20
• jiangjing
直接等于 C(100，10+3+1)？
2019-04-25
• Joe
C++实现
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

class Combination {
private:
const int firstPrize;
const int secondPrize;
const int thirdPrize;

public:
Combination(int x, int y, int z)
: firstPrize(x), secondPrize(y), thirdPrize(z) {
}
/**
* @description:
* 从10个人中选出三等奖3人，二等奖2人，一等奖1人，不能重复获奖。
* @param {type} rewardNum- 指定赏金数， result- 奖赏方式结果。
* @return: null
*/
void rewardMethods(vector<int> result, vector<int> candidate) {
unsigned int len = thirdPrize + secondPrize + firstPrize;
if (result.size() == len) {
// 输出结果
resultOutput(result);
return;
} else {
for (unsigned int i = 0; i < candidate.size(); i++) {
vector<int> resultNew = result;
resultNew.push_back(candidate[i]);

vector<int> candidateNew;
copyElem(candidate, candidateNew, i + 1);
rewardMethods(resultNew, candidateNew);
}
}
}
// 数据复制函数
void copyElem(vector<int>& input, vector<int>& output, int i) {
vector<int>::iterator it = input.begin() + i;
for (; it < input.end(); it++) {
output.push_back(*it);
}
}
// 数据复制函数
void copyElem(vector<int>& input, vector<int>& output, int i) {
vector<int>::iterator it = input.begin() + i;
for (; it < input.end(); it++) {
output.push_back(*it);
}
}
// 输出结果
void resultOutput(vector<int> res) {
for (unsigned int i = 0; i < res.size(); i++) {
if (i == thirdPrize) cout << '*';
if (i == thirdPrize + secondPrize) cout << '*';
cout << res[i] << ' ';
}
cout << endl;
}
};

// test
int main(void) {
Combination test(1, 2, 3);
vector<int> res;
vector<int> candidate;
// 输入
for (unsigned int i = 0; i < 10; i++) {
candidate.push_back(i + 1);
}
test.rewardMethods(res, candidate);
}
2019-01-10

29