找回密码
 注册
搜索
热搜: 回贴
  • 前程无忧官网首页 有什么好的平台可以
  • 最新的销售平台 互联网营销的平台有哪
  • 制作网页的基本流程 网页制作和网页设
  • 【帝国CMS】输出带序号的列表(数字排
  • 网站建设公司 三一,中联,极东泵车的
  • 织梦 建站 织梦网站模版后台怎么更改
  • 云服务官网 哪些网站有免费的简历模板
  • 如何建网站要什么条件 建网站要用什么
  • 吉林市移动公司电话 吉林省退休人员网
  • 设计类毕业论文 网站设计与实现毕业论
查看: 204|回复: 1

[原创]算法:combination in c++

[复制链接]
发表于 2009-11-3 01:43:36 | 显示全部楼层 |阅读模式 IP:江苏扬州
*/ --------------------------------------------------------------------------------------
*/ 出自: 编程中国 http://www.bc-cn.net
*/ 作者: aipb2007 E-mail:aipb@163.com
*/ 时间: 2007-8-26 编程论坛首发
*/ 声明: 尊重作者劳动,转载请保留本段文字
*/ --------------------------------------------------------------------------------------

前几天在论坛看到一个帖子,计算组合数,有点数学基础的都知道,求组合用公式Cnr(= n!/(n-r)!r!)可以得到组合数。怎样通过程序实现得到每一个组合序列呢?以整型数据为例:
Ex:
N = {1,2,3,4,5}
从N中5个元素取2个得到
12 13 14 15 23 24 25 34 35 45 ——10个组合
这里可以看到组合出现是有规律的,每个组合总是按N中元素顺序出现(组合不是排列,12和21属于同一组合),其次,相邻组合后者在前者基础上从最末元素开始按N中元素顺序递增。
这是个很有用的信息,如果我们要输出每个组合序列,我们可以很自然的联想到最直观的解决办法——递归回溯。论坛上那位朋友也是用的这个思想设计解法。
现给出代码,在长度为N顺序整型数据中选取长度为R的组合序列:
//参数说明:a记录组合序列,k1为组合坐标,k2为辅助参数
void combination(int a[],int n,int r,int k1,int k2){
if (k1 == r){ //输出当前序列
for (int i = 0;i < r;++i)
cout << a[i] << " ";
cout << endl;
}
else
for (int i = k2;i < n;++i){
a[k1] = i+1; //子序列赋值
combination(a,n,r,k1+1,i+1); //递归回溯
}
}

代码很简单。这个问题现在可以算解决了吧?不然,由此我想到,如果当前集合N并非顺序排列,如果要想对每次得到的R序列做特定处理。那么仅仅这样是不够的。为了增加实用性,如果把它设计成一个泛型算法,是否效果更好。
有了初步设想,进一步考虑,N序列应该由用户定义,用容器R来储存组合序列,并由用户设定对当前R中组合序列的操作。

下面是模板函数:
//参数说明:begin,end分别为双向迭代器,col为坐标,初始为0,loop循环次数,由N,R长度差决定,func 用户定义函数
template<class BidIt,class Func>
void combination_recursive(BidIt n_begin,BidIt n_end,int n_col,
BidIt r_begin,BidIt r_end,int r_col,int loop,Func func){
int r_size = r_end-r_begin; //获取R长度
int curr_n_col = n_col;
int curr_loop = loop;

if (r_col == r_size) //产生组合序列
func(r_begin,r_end);

else
for (int i = 0;i <= loop;++i){

BidIt r_it = r_begin; //获取R迭代器位置
for (int r_cnt = 0;r_cnt < r_col;++r_cnt)
++r_it;
BidIt n_it = n_begin; //获取N迭代器位置
for (int n_cnt = 0;n_cnt < n_col+i;++n_cnt)
++n_it;

*r_it = *n_it; //赋值

++curr_n_col;
//递归回溯
combination_recursive(n_begin,n_end,curr_n_col,
r_begin,r_end,r_col+1,curr_loop,func);
--curr_loop;
}
}
函数用法:
Ex:
//自定义函数,这里为输出
void display(char *b,char *e){
cout << b << endl;
}

int main(){
char n[] = "abcdef";
char r[] = "xxx";
combination_recursive(n,n+6,0,r,r+3,0,6-3,display);
system("pause");
}
到这里,最初的设想得以实现。但是又存在一个问题,算法combination用到了递归,在大规模的输入时,入栈的深度会消耗大量的内存空间,其次,尽管我们自定义的函数可以实现需要的操作,但是用途是很有限的,并且不能灵活的筛选需要的组合序列。
与“组合”相关的字眼就是“排列”了,在STL算法库中,next_permutation是个很好的范例(参见blog中另一文章《stl算法:next_permutation剖析》),能否设计一个类似这样的范型算法解决我们的问题?答案是肯定的。因为在最初的例子中得出组合的两个性质,说明组合间是有序的,由一个组合序列是可以得出下一个组合序列的。
下面是combination的函数原型:

template<class BidIt>
bool next_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end);

template<class BidIt,class Pred>
bool next_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end
Pred equal);

template<class BidIt>
bool prev_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end);

template<class BidIt,class Pred>
bool prev_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end,
Pred equal);

算法在线性时间内完成,并且采用迭,由于算法具体实现很繁杂,这里只做简要说明。next_combination & prev_combination均采用从末端向前索引,根据比较N,R当前元素设置标记并产生下一组合序列。

函数用法:
Ex:
#include <iostream>
#include "combination.h"
using namespace std;
int main(){
char n[] = "abcdefg";
char r[] = "abc";
int count = 0;
do{
cout << r << endl;
++count;
}
while (next_combination(n,n+7,r,r+3));
cout << count << endl;
cout << "finished" << endl;
system("pause");
}

若采用prev_combination,则需替换r为最大组合序列char r[] = “efg”。
注:本文算法虽全由我书写完成但并非全由我设计,借鉴于网络和书籍,欢迎讨论。


源代码下载:


附件: 只有本站会员才能下载或查看附件,请您 登录 或 注册
发表于 2009-11-3 01:43:37 | 显示全部楼层 IP:江苏扬州
自己支持一个,就在我自己bccn博客上发表过,可以算原创吧?
老大觉得不妥先知会一声,我有原创恐惧症啊!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|最新主题|手机版|微赢网络技术论坛 ( 苏ICP备08020429号 )

GMT+8, 2024-9-30 07:27 , Processed in 0.210839 second(s), 12 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表