SW정리: 조합 (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:

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:

SW정리

2016년 3월 5일 토요일

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

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

댓글 4개: