组合生成组合的生成之生成下一个组合 By ACReaper

这段时间一直在研究组合生成之类的问题,现在正好有机会和大家共享一下.

    生成下一个组合，其实道理很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 
#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]);elseprintf("%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

文章结束给大家分享下程序员的一些笑话语录： 关于编程语言
如果 C++是一把锤子的话，那么编程就会变成大手指头。
如果你找了一百万只猴子来敲打一百万个键盘，那么会有一只猴子会敲出一 段 Java 程序，而其余的只会敲出 Perl 程序。
一阵急促的敲门声，“谁啊！”，过了 5 分钟，门外传来“Java”。
如果说 Java 很不错是因为它可以运行在所有的操作系统上，那么就可以说 肛交很不错，因为其可以使用于所有的性别上。

转载于:https://www.cnblogs.com/xinyuyuanm/archive/2013/05/03/3057362.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！