組合的生成之生成下一個組合 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次就可以了！

代碼如下:

[cpp]
#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; 
}  

#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