精选留言(61)

• 
  罗耀龙@坐忘

  2020-03-31

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

  展开

  作者回复: 关于婚姻的点，要点赞👍

  共 2 条评论

  26
• 
  风轨

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

  展开

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

  共 4 条评论

  21
• 
  cwtxz

  2019-12-26

  老师的这节课更让我加深了编程思维本质是数学思维的观点。各种各样的if和else语句，实质是从所有可能的集合之中选择符合条件的小集合。各种各样的循环语句实质是从集合里面筛选符合某种条件的集合。这些例子不胜枚举。所以说，数学思维的灵活程度决定了你代码的优雅程度与质量高低，进而影响你的职业极限。数学思维越好，代码的生命才会更健壮，你的职业瓶颈才能越容易被打破，你的生涯才能走得越高远，所以，学数学，会让你的代码功底更强。

  展开

  

  10
• 
  Wing·三金

  2018-12-31

  思路一： 先运行combine(100, 1)，将所有结果保存。然后用一层迭代对每个结果运行combine(99, 3)，将所有结果append进去。 然后再来一层迭代对上一结果运行combine(96, 10)，同样依次append进去。 此处的关键点在于每个迭代下得将上一结果中的数拿掉，以及得保存临时结果。 此思路也等价于直接上三个嵌套循环+运行递归程序。 思路二： 先运行combine(100, 14)，对每个结果运行combine(14, 10)，再对每个更新的结果运行combine(4, 3)。其实就是思路一逆过来。 理论上二者的复杂度是一样的，用scipy验证了下确实如此。

  展开

  共 1 条评论

  11
• 
  行者

  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, [])

  展开

  共 1 条评论

  8
• 
  夏微凉

  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

  共 4 条评论

  6
• 
  Paul Shan

  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号元素）递归调用

  展开

  

  5
• 
  qinggeouye

  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_[0]) for k1 in lucky1: total2 = copy.copy(total) for j1 in k1: total2.remove(j1) lucky2 = lucky_draw_combination(total2, m_[1]) for k2 in lucky2: total3 = copy.copy(total2) for j2 in k2: total3.remove(j2) lucky3 = lucky_draw_combination(total3, m_[2]) for k3 in lucky3: print(k1, k2, k3)

  展开

  

  4
• 
  Ricky

  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; } ******************结果******************** Awards Notification Prize 1: 2 Prize 2: 0 6 Prize 3: 8 3 1 Awards Notification Prize 1: 2 Prize 2: 0 6 Prize 3: 8 3 4 Awards Notification Prize 1: 2 Prize 2: 0 6 Prize 3: 8 3 5 Awards Notification Prize 1: 2 Prize 2: 0 6 Prize 3: 8 3 7

  展开

  共 1 条评论

  4
• 
  天涯不是咫尺

  2020-04-13

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

  作者回复: 因为自己不会和自己踢，所以选定主场球队之后，客场就只有31种选择。同样，如果先选择客场，那么也有32种选择，但是主场就只有31种了

  

  3
• 
  Mr.L

  2020-05-07

  class lucky: def get_lucky_num(self, rest, result): if len(result) == 14: print(result) return for i,k in enumerate(rest): result2 = result.copy() result2.append(k) rest2 = rest[i+1:] self.get_lucky_num(rest2, result2) #test: rest = range(1,101) result = list() lucky().get_lucky_num(rest,result)

  展开

  共 1 条评论

  2
• 
  Duke

  2021-09-09

  // 课后作业 .Net 实现 void Main() { prize.Sum(i => total += i); Combine(Enumerable.Range(1, 8).ToList<int>(), null); Console.WriteLine($"\n total:{count}"); } static int count = 0; static List<int> prize = new List<int> { 1, 2, 1 }; // （8）*（7）*(6*5/2) = 8 * 7 * 15 = 840 //new List<int> { 3, 1 }; // 8*7*6/3*2）* (5) = 280 static int total = 0; // 总奖项数 // 组合取出所有获奖人数 static void Combine(List<int> sourceList, List<int> destList) { if (destList == null) destList = new List<int>(); // 获取一个完整的获奖组合后，将他们排序 if (destList.Count == total) { Permutation(destList, null); return; } sourceList.ForEach( item => { var newDestList = destList.Take(destList.Count).ToList(); newDestList.Add(item); var newSourceList = sourceList.Skip(sourceList.FindIndex(s => s.Equals(item)) + 1).ToList(); Combine(newSourceList, newDestList); }); } // 将获取人数按照奖项排序 static void Permutation(List<int> sourceList, List<int> destList) { if (destList == null) destList = new List<int>(); // 获取一个完整按照奖项排序后的组合，将结果打印 if (destList.Count == total) { count++; var str = ""; destList.ForEach(l => str += l + ","); str = str.TrimEnd(','); Console.WriteLine(str); return; } if (destList == null) destList = new List<int>(); sourceList.ForEach(item => { var newDestList = destList.Take(destList.Count).ToList(); newDestList.Add(item); var newSourceList = new List<int>(); // 同一奖项多人不区分顺序：如果当前和前一位都处于同一奖项的位置（通过奖项集合下标判断），忽略该记录 var currentIndex = newDestList.Count - 1; if (newDestList.Count > 1 && prize[GetPrizeIndex(newDestList.Count - 1)] > 1 && prize[GetPrizeIndex(newDestList.Count)] > 1 && newDestList[currentIndex] < newDestList[currentIndex - 1]) return; newSourceList = sourceList.Where(s => !s.Equals(item)).ToList(); Permutation(newSourceList, newDestList); }); } static int GetPrizeIndex(int num) { var index = 0; for (int i = 0; i < prize.Count; i++) { num -= prize[i]; if (num <= 0) { index = i; break; } } return index; }

  展开

  

  1
• 
  Geek_c23a4c

  2021-01-02

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

  作者回复: 对，这里举出组合可能的不同应用场景，多元文法和销售维度没有联系

  

  1
• 
  Ball

  2020-08-05

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

  作者回复: 数学思维很重要，多多学习和运用，你会发现更多妙用

  

  1
• 
  teddytyy

  2019-12-05

  100！/（90！*10！） * 90！/（87！*3！） * 87

  

  2
• 
  Paul Shan

  2019-08-20

  思考题 C(100,14) C(14,10)C(4,3)种可能性

  

  1
• 
  flow

  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-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
• 
  Youngggg

  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, [], [], []) 运行结果： 一等奖 [1] 二等奖 [2, 3] 三等奖 [4, 5, 6] .....

  展开

  

  1
• 
  013923

  2022-07-28 来自北京

  学习了！

  

  