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;
}
