排列组合问题
<div id="cnblogs_post_body"> 排列：从n个不同元素中，任取m(m<=n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m<=n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m)表示。 A(n,m)=n(n-1)(n-2)&hellip;&hellip;(n-m+1)= n!/(n-m)! 此外规定0!=1组合：从n个不同元素中，任取m(m<=n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m<=n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号C(n,m) 表示。 C(n,m)=A(n,m)/m!=n!/((n-m)!*m!)；C(n,m)=C(n,n-m)。
<div class="cnblogs_code">#include <iostream>using namespace std;#define MaxN 10char used;int p;char s;//从n个元素中选r个进行排列void permute(int pos,const int n,const int r){ int i; /*如果已是第r个元素了，则可打印r个元素的排列 */ if(pos == r) { for(i=0; i<r; i++) cout<<s]; cout<<endl; return; } for (i=0; i<n; i++) { if(!used) { /*如果第i个元素未用过*/ /*使用第i个元素，作上已用标记，目的是使以后该元素不可用*/ used = 1; /*保存当前搜索到的第i个元素*/ p = i; /*递归搜索*/ permute(pos+1,n,r); /*恢复递归前的值，目的是使以后改元素可用*/ used = 0; } }}//从n个元素中选r个进行组合void combine(int pos,int h,const int n,const int r){ int i; /*如果已选了r个元素了，则打印它们*/ if (pos == r) { for(i=0; i<r; i++) cout<<s]; cout<<endl; return; } for(i=h; i<=n-r+pos; i++) /*对于所有未用的元素*/ { if (!used) { /*把它放置在组合中*/ p = i; /*使用该元素*/ used = 1; /*搜索第i+1个元素*/ combine(pos+1,i+1,n,r); /*恢复递归前的值*/ used = 0; } }}//产生0~2^r-1的二进制序列void binary_sequence(int pos,const int r){ inti; if(pos == r) { for(i=0; i<r; i++) cout<<p; cout<<endl; return; } p = 0; binary_sequence(pos+1,r); p = 1; binary_sequence(pos+1,r);}//利用上面的二进制序列打印字符串的所有组合//如"abc"输出a、b、c、ab、ac、bc、abc。void all_combine(int pos,const int r){ inti; if(pos == r) { for(i=0; i<r; i++) { if(p==1) cout<<s; } cout<<endl; return; } p = 0; all_combine(pos+1,r); p = 1; all_combine(pos+1,r);}//利用r进制序列打印字符串的所有重复组合//如"abc"输出aaa、aab、aac、aba、abb、abc、aca、acb、acc...。void repeative_combine(int pos,const int r){ inti; if(pos == r) { for(i=0; i<r; i++) { cout<<s]; } cout<<endl; return; } for(i=0; i<r; ++i) { p = i; repeative_combine(pos+1,r); }}int main(){ strcpy(s,"ABC"); int n = 3; int r = 3; //permute(0,n,r); //combine(0,0,n,r); //binary_sequence(0,r); //cout<<"string: "<<s<<endl; //all_combine(0,r); //repeative_combine(0,r); return 0;}
页:
[1]