注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

C++生成组合  

2013-04-06 22:32:22|  分类: C/C++编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
程序使用的是《组合数学》中生成组合数的方法:
假設有5個元素的集合,取出3個元素的可能组合(P(5,3)=10,n=5,m=3)如下: 
{1 2 3}、{1 2 4 }、{1 2 5}、{1 3 4}、{1 3 5}、{1 4 5}、{2 3 4}、{2 3 5}、{2 4 5}、{3 4 5} 

生成這些子集一些規則: 
一、如果最右一個元素小於n,則不斷加1 
二、如果右邊一位已至该位置的最大值,則加1的位置往左移 
三、每次加1的位置往左移後,必須重新調整右邊的元素為遞增順序 

所以關鍵點就在於哪一個位置必須進行加1的動作,到底是最右一個位置要加1?還是其它的位置? 

在實際撰寫程式時,我們可以使用一個變數positon來記錄加1的位置,position的初值設定為m-1,在position位置的值若小於n就不斷加1,如果大於n了(或者执行加1操作后等于其右边的数),position就減1,也就是往左移一個位置;由於位置左移後,右邊的元素會經過調整,所以我們必須檢查从最右邊往左的元素是否小於n或者满足执行加1操作后小于其右边的数,如果是,則position調整成该数的位置,如果不是,則positon維持不變。 
源程序:

/*
生成组合
*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/**
n: 原来的元素总个数
m: 生成的子排列的元素个数
*/
void combination(int n,int m)         //生成组合P(n,m)
{
if(0==n||0==m||n<m)         //检查输入的参数是否满足条件
{
exit(1);
}
int size=n;       
int position;    //对应数字需要加1的下标位置
long count=0;      //组合数计数
vector<int> vecOrder;      //存放组合的下标 如{1,2,3}  表示vecInput中的下标0,1,2对应的字符
for(int i=1;i<=m;i++)   //初始化组合的下标,如{1,2,3}
{
vecOrder.push_back(i);
}
    position=m-1;   //一开始从最右边开始执行加1操作
while(1)
{
count++;          //组合数加1
cout<<count<<": ";
cout<<"{";          //输出一个排列
for(int i=0;i<m;i++)
{
cout<<vecOrder[i]<<" ";
}
cout<<"}"<<endl;
if(vecOrder[0]==(size-m+1))   //表示已经到了最后一个排列
{
break;
}
if((position==m-1&&vecOrder[position]<size)||(position<m-1&&vecOrder[position]+1<vecOrder[position+1])) //要求最右边的数字不等于size才加1&&不是最右边的数字加1后小于其右边的数
{
vecOrder[position]++;
continue;
}
else
{
position--;            //往左移一位
if(vecOrder[position]+1==size)      //若该位置的数不符合加1操作,则继续往左移一位
{
position--;
}
vecOrder[position]++;    //更新该位置的数,并更新其右边所有位置的数(依次为前面的数加1)
for(int i=position;i<m-1;i++)
{
vecOrder[i+1]=vecOrder[i]+1;
}
for(int i=m-1;i>position;i--)   //从最右向左检查position后面的数是否小于size,若有小于size的,则更新position为该数的位置,否则position大小不变
{
                 if((i==m-1&&vecOrder[i]<size)||(i<m-1&&vecOrder[i]+1<vecOrder[i+1]))  //需要判断是否是最右边的数
{
position=i;
break;
}
}
}
}
}
int main()
{
    vector<char> vecInput;
char tempchar;
int n,m;
cin>>n>>m;
/*
while(n--)
{
cin>>tempchar;
vecInput.push_back(tempchar);
}
*/

combination(n,m);
}

结果示例:
C++生成组合 - changfengmingzhi - 长风明志的博客
 
以上是输出位置信息,下面是直接输出原来集合生成的组合:

/*
生成组合
*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/**
n: 原来的元素总个数
m: 生成的子排列的元素个数
*/
void combination(vector<char> vecInput,int n,int m)         //生成组合P(n,m)
{
if(0==n||0==m||n<m)         //检查输入的参数是否满足条件
{
exit(1);
}
int size=n;       
int position;    //对应数字需要加1的下标位置
long count=0;      //组合数计数
vector<int> vecOrder;      //存放组合的下标 如{1,2,3}  表示vecInput中的下标0,1,2对应的字符
for(int i=1;i<=m;i++)   //初始化组合的下标,如{1,2,3}
{
vecOrder.push_back(i);
}
    position=m-1;   //一开始从最右边开始执行加1操作
while(1)
{
count++;          //组合数加1
cout<<count<<": ";
cout<<"{";          //输出一个排列
for(int i=0;i<m;i++)
{
cout<<vecInput[vecOrder[i]-1]<<" ";
}
cout<<"}"<<endl;
if(vecOrder[0]==(size-m+1))   //表示已经到了最后一个排列
{
break;
}
if((position==m-1&&vecOrder[position]<size)||(position<m-1&&vecOrder[position]+1<vecOrder[position+1])) //要求最右边的数字不等于size才加1&&不是最右边的数字加1后小于其右边的数
{
vecOrder[position]++;
continue;
}
else
{
position--;            //往左移一位
if(vecOrder[position]+1==size)      //若该位置的数不符合加1操作,则继续往左移一位
{
position--;
}
vecOrder[position]++;    //更新该位置的数,并更新其右边所有位置的数(依次为前面的数加1)
for(int i=position;i<m-1;i++)
{
vecOrder[i+1]=vecOrder[i]+1;
}
for(int i=m-1;i>position;i--)   //从最右向左检查position后面的数是否小于size,若有小于size的,则更新position为该数的位置,否则position大小不变
{
                 if((i==m-1&&vecOrder[i]<size)||(i<m-1&&vecOrder[i]+1<vecOrder[i+1]))  //需要判断是否是最右边的数
{
position=i;
break;
}
}
}
}
}
int main()
{
    vector<char> vecInput;
char tempchar;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>tempchar;
vecInput.push_back(tempchar);
}
combination(vecInput,n,m);
}

输出示例:
C++生成组合 - changfengmingzhi - 长风明志的博客
 





  评论这张
 
阅读(806)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017