[C언어] 조합

 

N개의 item에서 M개를 뽑고자 할 때 가능한 모든 방법을 출력하는 프로그램을 작성하시오.

 

다음과 같은 문제에서 뽑는 방법에 따라 여러가지 프로그램을 만들 수 있다.

뽑는 방법은 중복 여부/순서 고려에 따라 나눌 수 있고 그 경우는 다음과 같다.

 

- 중복 불가능

1. 조합(순서와 상관 없음)

2. 순열(순서와 상관 있음)

 

- 중복 가능(같은 item을 여러 번 뽑을 수 있음)

3. 중복 조합

4. 중복 순열

 

ex. 5개의 item에서 3개를 뽑고자 할 때 모든 방법을 사용하여 가짓수를 구하시오.

- 인덱스로 프로그램을 진행하므로 아이템의 내용물과 관계없이 순번으로 기입.

 

1. 조합 : 순서가 중요하지 않지만, 중복 없이 3개씩 뽑는다.

{0,1,2}

{0,1,3}

{0,1,4}

{0,2,3}

{0,2,4}

{1,2,3}

{1,2,4}

{1,3,4}

{2,3,4}

 

5C3 = 10

 

2. 중복 조합 : 순서가 중요하지 않지만, 중복하여 3개씩 뽑는다.

{0,0,0}

{0,0,1}

{0,0,2}

{0,0,3}

{0,0,4}

{0,1,0}

. .  

{3,4,4}

{4,4,4}

 

3. 중복 순열 : 순서가 중요하며, 중복하여 3개씩 뽑는다.

{0,0,0}

{0,0,1} 

{0,0,2}

{0,0,3}

{0,0,4}

{0,1,0}

{0,1,1}

{0,1,2}

{0,1,3}

{0,1,4}

...

 

5X5X5 = 125

 

4. 순열 : 순서가 중요하지만, 중복하지 않고 3개를 뽑는다.

{0,1,2}

{0,1,3}

{0,1,4}

{0,1,2}

{0,2,3}

{0,2,4}

{0,3,1}

{0,3,4}

{0,4,1}

{0,4,2}

{0,4,3}

{1,0,2}

...

 

5P3 = 5X4X3 = 60

 

문제 해결 방법

 

1. M개를 뽑아서 담을 수 있는 공간을 미리 할당 (buket)

 

2. 함수를 다음과 같이 구현.

pick(item 정보, buket 정보, k)

-k : 앞으로 뽑아야 할 크기

-trivial case (if k=0)

: M개를 뽑아야 할 문제인데 이미 M개를 다 뽑은 경우 적절한 일을 해주고 return한다. (무한 호출 막음)

-recurisve case (if k>0)

:앞으로 k를 뽑아야 하므로 일단 1개를 먼저 뽑고, 같은 함수를 이용하여 k-1개를 더 뽑는다.

:1개를 뽑는 방법은 순열/조합/중복순열/중복 조합에 따라 다름.

 

#1 조합(Combination)

void pick(int n, int* bucket, int buketSize, int k){

            int i, lastIndex, smallest, item;

            it(k==0){

                        for(i=0, i<buketSize; i++)

                                    printf("%d", buket[i]); // 4개 다 뽑았으면 printf

                        printf("\n");

                        return; // 무한 반복을 막기 위해 필수.

            }

            lastIndex = bucketSize - k -1;



            if (bucketSize == k) // 처음 뽑을 때

                        smallest = 0;

            else

                        smallest = bucket[lastIndex] + 1; // 최근에 뽑은 수 + 1 (오름차순)



            for(item = smallest; item<n; item++){

                        bucket[lastIndex+1] = item; // smallest ~ n까지 모든 경우의 수 구함.

                        pick(n,bucket,buketSize,k-1) // 나머지 자리수는 재귀함수를 불러 구함. 

            }

            return; // 생략 가능. item이 n이상일 경우 printf되지 않고 소멸.

}

 

#중복 조합(Combination with Repetition)

- 논리 흐름은 조합과 같지만, 중복 조합의 경우 오름차순으로 뽑을 때 본인 것까지 포함하여 뽑음

 

void pick(int n, int* bucket, int buketSize, int k){

            int i, lastIndex, smallest, item;

            it(k==0){
                        for(i=0, i<buketSize; i++)
                                    printf("%d", buket[i]); // 4개 다 뽑았으면 printf
                        printf("\n");
                        return; // 무한 반복을 막기 위해 필수.
            }

            lastIndex = bucketSize - k -1;

            if (bucketSize == k) // 처음 뽑을 때
                        smallest = 0;
            else
                        smallest = bucket[lastIndex]; // 최근에 뽑은 수(본인 것 포함/오름차순)

            for(item = smallest; item<n; item++){

                        bucket[lastIndex+1] = item; // smallest ~ n까지 모든 경우의 수 구함.
                        pick(n,bucket,buketSize,k-1) // 나머지 자리수는 재귀함수를 불러 구함. 

            }
            return; // 생략 가능. item이 n이상일 경우 printf되지 않고 소멸.
}

#중복순열(Permutation with Repetition)

- 새 item을 뽑을 때 매번 전체 아이템 중에서 뽑음.

 

void pick(int n, int* bucket, int buketSize, int k){

            int i, lastIndex, smallest, item;

            it(k==0){

                        for(i=0, i<buketSize; i++)

                                    printf("%d", buket[i]); // 4개 다 뽑았으면 printf

                        printf("\n");

                        return; // 무한 반복을 막기 위해 필수.

            }

            lastIndex = bucketSize - k -1;



            smallest = 0; // 전체 아이템에서 뽑음.



            for(item = smallest; item<n; item++){

                        bucket[lastIndex+1] = item; // smallest ~ n까지 모든 경우의 수 구함.

                        pick(n,bucket,buketSize,k-1) // 나머지 자리수는 재귀함수를 불러 구함. 

            }

            return; // 생략 가능. item이 n이상일 경우 printf되지 않고 소멸.

}

#순열(Permutation)

 

void pick(int n, int* bucket, int buketSize, int k){

            int i, lastIndex, smallest, item;

            it(k==0){

                        for(i=0, i<buketSize; i++)

                                    printf("%d", buket[i]); // 4개 다 뽑았으면 printf

                        printf("\n");

                        return; // 무한 반복을 막기 위해 필수.

            }

            lastIndex = bucketSize - k -1;



            smallest = 0; // 전체 아이템에서 뽑음. 단, 안 뽑힌 아이템 중에서 뽑는다.



            for(item = smallest; item<n; item++){

                        int choose = 0;

                        // choose로 뽑힌 아이템들 중 중복되는 게 있는지 확인. 

                        for(int i=0; i<lastIndex+1; i++)

                                    if(item == bucket[i]){

                                                choose = 1;

                                                break;

                                    }

                        // 중복되는 게 없는 경우 해당 순번 아이템을 bucket에다가 넣음.

                        if(choose==0){     

                                    bucket[lastIndex+1] = item; 

                                    pick(n,bucket,buketSize,k-1) 

                        }

            }

}