首页 > > 程序设计 > C/C++ >

算法：combination in c

2008-02-23 05:40:36来源：互联网阅读 ()

原帖及讨论：http://bbs.bc-cn.net/dispbbs.asp?boardid=56&id=165455

*/ --------------------------------------------------------------------------------------
*/ 出自：编程中国 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";

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有