조합 (Combination) 알고리즘 생성 방법 algorithm알고리즘

조합 : 순서를 고려하지 않는 나열

nCr = n!/(n-r)!r!

3C2 = 3!/1!2! =3*2/(2) = 3
{1,2,3}
3개
{1,2}
{2,3}
{1,3}

3C3 = 3!/0!3! = 1
{1,2,3}

4C2 = 4!/(2!*2!) = 4*3*2*1/(2*2) = 6
{1,2,3,4}
6개
{1,2} *
{1,3} *
{1,4}
{2,3} *
{2,4}
{3,4}

이건 단순 for loop로 만들어 낼 수 있을까?
규칙성이 복잡해서 만들어 낼 수는 있겠지만 조금 까다롭네요.

4C2 를 고민해보도록 하겠습니다.

위의 마지막 식은 일반적으로 갯수를 나타내는 수식입니다. 하지만 여기에서는 select 부분을 중점을 두면, 마지막 item을 선택할때와 하지 않을때를 선택해서 하위 단위의 재귀를 호출하는 방법을 고민할 수 있습니다.

수도 코드로 만들어보면 아래와 같습니다.
flag는 각 상태를 선택했는지를 표시합니다. 위 그림에서는 O 로 표기했다는 의미입니다.

combination(n,r)
{
    if(n==1){
        print data
        return;
    }
    if(n==r){
        print data
        return;
    }
    flag[n-1]=1    <= 마지막 item을 선택함
    combination(n-1,r-1)
    flag[n-1]=0    <= 마지막 item을 선택하지 않음
    combination(n-1,r)
}

아래는 C언어로 작성한 코드입니다.
출력할때는 n=r이 같으면 화면에 n갯수만큼 모두 나와야 합니다.
r=1이 되면 n개의 아이템을 하나씩 선택해 줍니다.

C, pasted 1 second ago:  #include <stdio.h> int data[]={1,2,3,4}; int flag[]={0,0,0,0}; int length = 4; int combination(n,r) { if( n == r ){ int i; for(i=0;i<n;i++){ flag[i] = 1; } for(i=0;i<length;i++){ if( flag[i] == 1 ) printf("%d ",data[i]); } for(i=0;i<n;i++){ flag[i] = 0; } printf("\n"); return 0; } if( r==1 ){ int i,j; for(i=0;i<n;i++){ flag[i] = 1; for(j=0;j<length;j++){ if( flag[j] == 1 ) printf("%d ",data[j]); } flag[i] = 0; printf("\n"); } return 0; } flag[n-1]=1; combination(n-1,r-1); flag[n-1]=0; combination(n-1,r); } int main() { combination(4,2); return 0; } Output: 1 4 2 4 3 4 1 3 2 3 1 2

C, pasted just now:  #include <stdio.h> int data[]={1,2,3,4,5,6}; int flag[]={0,0,0,0,0,0}; int length = 6; int combination(n,r) { if( n == r ){ int i; for(i=0;i<n;i++){ flag[i] = 1; } for(i=0;i<length;i++){ if( flag[i] == 1 ) printf("%d ",data[i]); } for(i=0;i<n;i++){ flag[i] = 0; } printf("\n"); return 0; } if( r==1 ){ int i,j; for(i=0;i<n;i++){ flag[i] = 1; for(j=0;j<length;j++){ if( flag[j] == 1 ) printf("%d ",data[j]); } flag[i] = 0; printf("\n"); } return 0; } flag[n-1]=1; combination(n-1,r-1); flag[n-1]=0; combination(n-1,r); } int main() { combination(6,3); return 0; } Output: 1 5 6 2 5 6 3 5 6 4 5 6 1 4 6 2 4 6 3 4 6 1 3 6 2 3 6 1 2 6 1 4 5 2 4 5 3 4 5 1 3 5 2 3 5 1 2 5 1 3 4 2 3 4 1 2 4 1 2 3