• 2018-12-31
从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]
*
*/
}
}
展开

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

1
9
• 2019-01-02
案例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, [])
展开
6
• 2018-12-31
思路一：
先运行combine(100, 1)，将所有结果保存。然后用一层迭代对每个结果运行combine(99, 3)，将所有结果append进去。
然后再来一层迭代对上一结果运行combine(96, 10)，同样依次append进去。
此处的关键点在于每个迭代下得将上一结果中的数拿掉，以及得保存临时结果。

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

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

理论上二者的复杂度是一样的，用scipy验证了下确实如此。
展开
5
• 2019-01-10
#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
展开
4
• 2019-02-10
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)
展开
3
• 2019-08-21
总结
排列的递归公式是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号元素）递归调用
展开
2
• 2019-12-26
老师的这节课更让我加深了编程思维本质是数学思维的观点。各种各样的if和else语句，实质是从所有可能的集合之中选择符合条件的小集合。各种各样的循环语句实质是从集合里面筛选符合某种条件的集合。这些例子不胜枚举。所以说，数学思维的灵活程度决定了你代码的优雅程度与质量高低，进而影响你的职业极限。数学思维越好，代码的生命才会更健壮，你的职业瓶颈才能越容易被打破，你的生涯才能走得越高远，所以，学数学，会让你的代码功底更强。
1
• 2019-04-16
// 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为三等奖
展开
1
• 2019-01-14
黄老师，我这几天一直在纠结思考题，总共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

1
• 2019-01-04
使用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;
}
展开

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

1
• 2019-01-02
由于数量过大 设置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]
.....
展开
1
• 2020-01-07
老师，我感觉这样也可以达到你的文中的那个例子的效果，但是节省了不少的空间了。
java

private static void combine_3(ArrayList<String> terms, ArrayList<String> result, int index, int m) {
if (result.size() == m) {
System.out.println(result);
return;
}
for (int i = index, len = terms.size(); i < len; i++) {
combine_3(terms, result, i+1, m);
result.remove(result.size() - 1);
}
}

展开

作者回复: 很好的优化👍

• 2019-12-05
100！/（90！*10！） * 90！/（87！*3！） * 87
• 2019-11-30
原来组合这么强大！
• 2019-11-15
// 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-10-27
简单地用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-23
老师那个 “red bluetooth mouse” 真是大开眼界了！ 其实把数学思维对应到程序解决方案这个过程才是最难的，就像程序员要把现实世界的问题抽象成代码一样。

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

• 2019-10-09
讲个段子
淘汰赛 14只球队输一场，第四名输两场。
刚好16场。
• 2019-08-20
思考题
C(100,14) C(14,10)C(4,3)种可能性
• 2019-06-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);
}
展开