GetCombination함수에 n, r의 자연수를 입력하면 coll에 조합방식을 문자열로 반환한다.
함수 리턴값은 조합의 개수이다.

GetCombination();
combination();

두 개의 함수를 구현하고 GetCombination을 call~!!


int GetCombination(int n, int r, CStringArray *coll)
{
      int count = 0;

      CString strTemp = L"";
      CString temp = L"";

      int *c= new int[r+1];   // c에 dynamic array를 이용해 입력받은 r값으로 array의 크기정해줌

 for( int i=1;i<r+1;i++)   // s[0]=1,s[1]=2,..........,s[r-1]=r 이런식으로 값을 할당해줌.
 {        // lexicographic order에 따라 첫번째 combination값을 만들어줌
         c[i-1]=i;
 }

 for( int i=0;i<r;i++)
 { 
       temp.Format( _T("%i"), c[i] - 1 );
       strTemp = strTemp + temp;
 }
       coll->Add( strTemp );
       count++;

 int k;
 k=combination(n,r);    // k는 n,r에대해 가질수 있는 총 Combination갯수를 구한 값

 for( int h=2;h<k+1;h++)
 {
      int m=r-1;
      int max_val=n;

  while(c[m]==max_val)
  {
         m=m-1;     // maximumvalue 값을 만족하는 배열 위치보다 -1작은 위치 m을 구함
         max_val=max_val-1;  // 예를들어 n=6 r=4일때 1256 이란 값이 들어오면 5와 6은 while구문
  }       // 내에서 max_value만족 따라서 m=1이란 5,6앞의 2의 배열의 위치 값을 반환함

  c[m]=c[m]+1;    // c[m]에값에 +1을 해준다.
  for(int j=m+1;j<r;j++)  // while구문이 실행될 경우 실행 c[m+1]부터 c[r-1]까지
  {       // 그 앞에 수의 +1값을 자신이 가짐 ex) c[m+1]=c[m]+1. c[m+2]=c[m+1]+1
   c[j]=c[j-1]+1;   // cobination값은 permutation에서 swap을 사용하는것과 같은것이 필요 없다.
  }       // 위의 m의 값을 구한후 그 구한 m을 위치로 갔는 배열 c[m]값 이후로 그 앞에 값의
         // +1씩만 해주만 lexicographic order을 만족하는 combination값이 나옴
  strTemp = L"";
  for(int i=0;i<r;i++)
  { 
   temp.Format( _T("%i"), c[i] - 1 );
   strTemp = strTemp + temp;
  }
  coll->Add( strTemp );
  count++;
 }

 delete [] c;
 return count;
}


int combination(int n, int r)
{
         int i;
         int kup = 1;          // 분자
         int kdown = 1;        // 분모

         for(i=n;i>n-r;i--)    //  분자 계산
             kup *= i;

        for(i=r;i>0;i--)       //  분모에 계산
              kdown *= i;

         return kup/kdown;
}

 

출처 : http://ultragom.tistory.com/entry/nCrcombination-구현하기