6 순열과 조합 : 조합의 구현

이전포스트

순열과조합: 순열의구현  

순열과 조합, 조합의 구현

이전 포스트에서는 순열을 구현해 보았는데요, 순열의 특징은 사전순으로 정렬하는데 있습니다. 그렇다면 조합의 경우는 어떨까요?

우선 조합은 다음과 같은 특징을 같습니다. 비트스트링을 생각해보죠, 해당 원소가 포함되는 곳엔 1, 아닌 곳은 0이 됩니다. 아래그림을 확인해보죠.

r-조합은 기본적으로 n개 중 r개를 선택한 원소들의 고유한 집합입니다. 따라서 위와 같은 비트 스트링으로 포함, 비포함으로 표현할 수 있습니다. 자, 우선 모든 조합을 고려해보죠.

그러니까 비트스링의 모든 경우의수요. 그렇다면 경우의수는 2^n 가지 입니다. 자, 우선 간단한 예제를 풀어볼까요?

예제 4

1010111 의 다음 비트스링은 뭔가?

정답

1010111의 다음 비트스트링은 1011000 이다.

어떻게 다음 비트스트링이 나올 수 있었을까요? 순열보다 쉽습니다.

구현내용도 간단합니다.

함수처럼 만들어서 다음처럼도 만들 수 있습니다. 코드는 포스트 아래에 첨부하겠습니다. ^^

r-조합 구하기 1

아직 우리가 하고 싶은 건 안했습니다. 하고싶은건 r-조합을 구현하는 건데요. n개의 원소 집합에서 r-조합을 오름차순으로 구하기 위해 맨 처음 조합을 정의해볼게요. 

r을 4라고 해보죠!

그럼, 1, 2, 3, 4 다음의 조합은 무엇일까요? 1, 2, 3, 5

어떻게 구할까요? 음..... 4를 1더해요? 예.

1, 2, 3, 5 다음의 조합은 무엇일까요? 1, 2, 3, 6

어떻게 구할까요... 음... 5를 1더해요.. 네..

1, 2, 3, 7 다음의 조합은 무엇일까요? 음.... 모르겠어요.

좋아요. 지금부터 r-조합을 정렬해서 출력하는 비밀을 가르쳐드리죠. r-조합은 다음과 같은 방법으로 오름차순으로- 생성해낼 수 있습니다. 

{1,2, 3, 4} 는 조합의 처음이고, 마지막 조합집합은 다음과 같습니다. {4, 5, 6, 7} . 여기서 {4, 5, 6, 7}은 모두다 n-r+i를 만족하는 것을 확인하세요, {7-4+1, 7-4+2, 7-4+3, 7-4+4} == {4, 5, 6, 7}

그러니까 조합은 {n-r+1, n-r+2, n-r+3, ... , n-r+r} 을 만족할 때까지 오름차순으로 이동하는겁니다. 

즉 n-r+i를 만족하지 않는것을 찾으면됩니다. 단, 맨 마지막 원소를요.

우선 맨처음 {1, 2, 3, 4}서 살펴보면 n-r+i  != a[i] 인 가장 마지막원소를 1증가시킵니다. 

{1, 2, 3, 4} 를 {4, 5, 6, 7}와 비교해서 안맞는 젤 마지막 녀석을 바꿉니다. 4를 1증가시키죠. 

{1, 2, 3, 7} 를 {4, 5, 6, 7}과 비교해서 안맞는 젤 마지막 녀석을 바꿉니다. 3을 1증가시키죠.

예?, 그럼 {1,2, 4, 7} 이에요... {1, 2, 4, 5}가 되야하지않나요? 네 맞습니다. 그러므로 1 증가시킨 인덱스 이후의 모든 것들을 1 증가시킨 해당 인덱스보다 차근차근 높게 설정해주면됩니다. 그러니까 {1, 2, 4 , 5}  가 되죠.

구현을 해보았습니다.

함수로 만들었을 때 결과물

2, 3, 7, 9, 11, 13, 17 의 3조합을 출력해볼까요?

눈치가 빨랐던 분들은 눈치 챘겠지만, C(n, r)을 이용하기위해선 r만큼 크기의 배열이 있어야하구요, 조합알고리즘은 실제로 r만큼 크기의 배열을 만지작거리면서 목적 배열에 접근하는 것을 알수있어요. main함수의 printf 함수의 인자 b[a[j]] 처럼요!

P(n, r) 구현하기!

우리가 이제까지 구현한것은 P(n, n)과 C(n, r) 이였는데요. 이제는 P(n, r)을 구현해볼거에요.

혹시 nPr = nCr * r! 임을 기억하시나요? 선택한 조합들의 사전식 정렬을 고려하기때문에 각각의 경우의수가 r!만큼 있는거죠. 

기억이 안난다면 여길 클릭

P (n,r)의 동작은 다음과 같습니다.   P(9, 3), where S={1, 2, 3, 4, 5, 6, 7, 8, 9}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

1 2 4
1 4 2
2 1 4
2 4 1
4 1 2
4 2 1 .....

P(n,r) = C(n,r) *r! 임을 우리가 수행했던 코드들을 모두 사용하면됩니다. 그러니까 이중 루프인것이죠. 간단한 메인 함수 내 구조를 스샷을 통해확인하시구요. 자세한 내용은 아래에 첨부한 코드 확인하세요!

마지막으로 한 topic만 더 보고 마무리 할 건데요. 조합을 구현하는데에 방법이 한 가지 더 있어요. 이제까지 살펴본건 인덱스를 이용하여, 모든 인덱스가 마지막인가? (예로, C(9,3)인경우 {0,1,2} -> {6,7,8} )라고 질문하며 계속 인덱스를 생성했습니다. 

이번에는 비트스트링(또는 배열)을 이용해 조합을 생성해볼겁니다.

조합 구현하기 2 

이번에는 순열을 구했던 알고리즘을 이용해서 구현해봅니다. 기억이 안난다면 여기를 클릭

순열 알고리즘은 기본룰이 가장 뒤쪽에서부터 오름차순이여야만 한다고 했습니다. 그렇지만, 동일한것도 오름차순이라고 가정한다면 아래와 같이 동작할겁니다. 예?

<순열 조합이제 그만해 이 자식아!>

그래도 계속해봅시다. 아래의 코드를 참고하여 생각해봅시다. 다른점은 부등호">"의 ">="로의 변화 뿐입니다.

그러나 효율적인 것은 이전의 조합알고리즘이 효율적이구요, 포스트는 이만 이정도로 줄이고 다음 포스트에선 경우의 수 응용인 다이내믹 프로그래밍으로 뵙겠습니다.

이번엔 소스가 좀있습니다.

소스보기

1

다음 순서의 비트스트링 생성하기(조합의 경우의수 다음과 같다. 또는 부분집합.)

2

모든 경우의수에 따른 비트스트링 생성 함수 (모든 조합의 경우의 수와 같다. 또는 부분집합)

3

본격적인 조합구현하기. 모든 C(n, r)을 나열한다.

4

조합 알고리즘의 사용법. 조합 알고리즘은 인덱스를 생성하는 알고리즘임을 알 수있다.

5

P(n, r) 생성 알고리즘. 조합의 경우의 수에서 *r! 즉, 조합의 각 경우의 모든 순열을 생성한다. 함수가 두개겹쳐있음을 볼 수 있다.

6

사실상 순열 생성알고리즘과 비트스트링(배열)을 이용해 모든 조합의 경우의 수를 구할 수 도있다....지만 비효율적임

추가 (윈도우환경 에서 확인가능하다)

비트스트링 순열로 조합과, 조합알고리즘의 시간을 비교한코드. 비트스트링으로 24C12 를 표현하는데 9초 걸리고, 조합알고리즘으로는 30C15 3초컷 

완전탐색(bruteforce) 문제보기

해당페이지로

다음포스트보기

경우의 수 (조합)을 구현하는 다양한 방법들