08 | 组合：如何让计算机安排世界杯的赛程？

茶艺师学编程 可以这么记： 排列—大家走到一块，还要比个高低 组合—大家聚到一起，就是有缘 生活中的一个例子，比如婚姻，就应该是组合，“我和你一起，怎么都好”，而不是“排列”，“你，都得听我的！”

从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[0] = 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] * */ } }

黄老师，我这几天一直在纠结思考题，总共10人，一等名1名，二等奖2名，三等3名，还是没有完全理解思路，希望老师方便的时候解答下

用组合思想来处理多元词组的问题确实妙

老师，为什么主场球队有32种选择，客场球队只有31种选择？

使用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; }

连锁店的销售业绩报表的例子不是太理解。意思是分店名称、所在城市、销售品类三个维度做组合来对不同的维度的组合进行统计吗？这个和上面多元文法的应用比起来没啥意思，感觉脱节了

组合是不考虑顺序的排列，但是应用的时候需要存储数据，存储的势必只是某种组合的某种排列方式，这时候就需要一个标准化的流程来保证同一种组合的不同排列都可以转换成标准的排列已完成程序的存储，检索和比对

看到了组合的实用性

多元文法的解法存在一个问题，用户的输入会有单词间前后顺序不同造成的语意上下文不同。