生成下一个组合,其实原理很easy,听我慢慢道来也~
在集合{1,2,3,4,...N}中生成r组合。我们假设当前生成的是{a1,a2,...ar},则当可以生成下一个组合时的极限条件就是ar还没达到最大那么ar继续加1,就是下一个组合,如果ar达到最大了,那么此时就要ar-1看是否达到最大,没有则加一,又因为a1 < a2 <.... < ar,也就是说接着在把后面的数都一次比前面一个数大一加上ar-1此时的新值,为什么呢?这样可能变小了,不会和前面的重复吗?当然是不会,因为ar-1更新时也满足a1 < a2 <.. < ar-1而再更新的ar必定比ar-1大,而且是连续的。也就是说对于{a1,a2,...ar}我们要从后检查它的哪一一些是满足达到了最大值的假设是在第ai个是最后一个满足的(我们从后向前检查),则有{ai.....ar}一定分别对应{n
- r + i....n},所以我们可以得出检查的语句可以这样写
int I = r;
while(ai == n - r + r)
i--;
ai = ai + 1;
这样i此时刚好在下个需要变动的位置,接着再对从i之后的位置,到r更新数据
int j = i + 1;
for(;j <= r;j++)
aj = ai + j - i
至于这里为什么又要这样,是因为下一个组合也满足a1 < a2 <.... < ar,而且我们求的是离它最近的下一个组合当然这样写了,所以求某个集合的所有r组合,只需要把这个代码
运行C(n,r)- 1次就可以了!
代码如下:
#include <stdio.h>
#define MAXN 1000
int A[MAXN];
int B[MAXN];
int main(){
int n,m;
while(scanf("%d%d",&n,&m) != EOF){//集合为{1,。。。。n},生成其所有m组合
if(n < m){
printf("输入错误!");
continue;
}
for(int i = 1; i <= n; i++)
A[i] = i;
for(int i = 1; i <= m; i++)
B[i] = i;
for(;;){
bool flag = true;
for(int i = 1; i <= m; i++){
if(B[i] != n - m + i)
flag = false;
if(i != m )
printf("%d ",B[i]);
else
printf("%d\n",B[i]);
}
if(flag)
break;
int i = m;
while(B[i] == n - m + i)
i--;
B[i] = B[i] + 1;
for(int j = i + 1; j <= m; j++){
B[j] = B[i] + j - i;
}
}
}
return 0;
}
2013 05 03
By ACReaper
分享到:
相关推荐
组合数学之排列组合生成算法,很好的学习组合排列算法的资料
排列组合生成器,支持筛选,存储采用h2数据库,后台采用springboot框架
C++实现生成组合算法
关键字生成工具 关键字 生成 组合工具 组合排列
计算机程序设计艺术(第4卷)第4册 (双语版)生成所有树组合生成和历史
excel VBA - 排列组合生成算法 - ,可快速生成指定项目的所有排列组合
PL_SQL生成双色球所有组合
可以随即生成20位以内的密码 可以生成一窜随即组合数字
随机字母组合,随机数生成工具 无广告纯洁版,生成数量不限,长度不限,不重复,可用于密码组生成。
Delphi写的NM排列组合,生成文本txt到指定目录,定义函数指针,生成N个数,输出N个数的全排列 ,OrderedCount为已经有输出顺序的数字。 比如 从Min=6开始选 (ToReachCount-NowNumCount)个数字(假设这个值为3)的话,也...
包含C#源码 关于C#中随机数生成器 生成不重复子字母组合的随机数 并保存成TXT
大师Donald E. Knuth(汉名高德纳)的著作,计算机程序设计与艺术第四卷4册:生成所有树组合生成的历史GeneratingAllTreesHistoryOfCombinatorGeneration(中英)
组合数学之EVEN法生成排列 学习组合数学的朋友可以参考一下
主要函数GetPassword(int digits):string 参数为所生成随机组合位数 比如说要生成10为随机数字字母组合,就string randomCode = GetPassword(10); 生成的结果有数字和大写、小写字母组合
excel文档,可以任意生成m选n的全部组合,速度还可以。
用一个二进制数表示数组中是否选中序列: 如:3选2的组合:011 101 110 自动生成下一个 和上一个组合。
在穷举可能经嵌运算生成极小基模的入树组合原则下,给出了三个入树组合删除法则,利用法则可删除大量不能生成极小基模的入树组合,从而实现简单有效计算一个确定复杂系统极小基模集的目的.根据二阶反馈环中流位变量、...
网络安全加密设计涉及的特殊排列组合生成算法,刘广亮,杜瑞卿,为了能够对网络安全加密设计涉及的一些特殊排列组合进行生成,本研究选择了可重复选择全排列、可重复选择组合、不尽相异元素的全
C#生成2位或N位不重复字母数字组合,位数可自己设置调整
直通车 关键词 组合生成器 做淘宝直通车的用得着