从n个数中m个数的所有组合.docx

《从n个数中m个数的所有组合.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本算法用于实现从一个含有n个数字的数组中，任意取其中m个元素的所有组合的实现情况，推导理由：以1,2,3,4,5数组为例，很明显，当只取一个元素时有5种，即单独的一个元素；取2个时候，就是C(5，2)=10种，即任意取2个数，以此类推。下面给出算法实现：1，单独存入一个元素，并存到所有组合中去；2，每加入一个新元素，则该新元素为一个单独的组合，同时，该新元素与（前面的）所有组合都可以组成一个新组合。即一步一步地每个加1。例如当前面的所有组合只有（1）时，存入一个2，则2单独存一下；然后2与1组成一个新组合，所有插入2以后，新

2、的所有组合就是：（1），（2），（1,2）；接下来插入新元素3，则元素3也可以单独成为一个组合存入，同时元素3还可以与前面的任意一个组成一个新组合，则插入3以后，新的所有组合为：（1），（2），（3），（1,3），（2,3）（1,2，3），以此类推。3.最后统计（排序）所有组合的个数，以及每一种组合中元素的个数。对应输出元素个数为m的组合即可。下面给出示例程序：/*vector>*/voidMy_zuhe(intn,intr){multimap>mm,mm2;vecto

3、rnn,temp,bb;vector>target;multimap>::iteratorpos;vector::iteratorita,ita_bb;typedefpair>pr;for(inti=1;i<=n;i++)bb.push_back(i);if(r>n)return;intm=1,k;ita_bb=bb.begin();temp.push_back(*ita_bb);mm.insert(pr(temp.s

4、ize(),temp));temp.clear();++ita_bb;while(ita_bb!=bb.end()){k=*ita_bb;for(pos=mm.begin();pos!=mm.end();++pos){temp=pos->second;temp.push_back(k);mm2.insert(pr(temp.size(),temp));temp.clear();}for(pos=mm2.begin();pos!=mm2.end();++pos)mm.insert(*pos);mm2.clear();temp.

5、push_back(k);mm.insert(pr(temp.size(),temp));temp.clear();++ita_bb;}for(pos=mm.begin();pos!=mm.end();++pos){if(pos->first==r){target.push_back(pos->second);}}sort(target.begin(),target.end());vector>::iteratortt_pos;cout<<"Inallwehave"<

6、kinds,andtheyare:"<0)cout<begin();ita!=tt_pos->end();++ita)cout<<*ita<<",";cout<<")";}//returntarget;}主函数调用为：#include"stdafx.h"#include"example23_app

7、ly_offer.h"voidmain(){My_zuhe(10,2);cout<

8、，正确答案应该是981。输入格式输入只有1行，为2个正整数，用一个空格隔开：kN（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。输出格式输出为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10^9）。（整数前不要有空格和其他符号）。样例输入样例输