[완전탐색]-순열, 조합, 부분집합
완전탐색은 크게 3가지.
- 순열(Permutation) : 순서대로 열을 세우는.
- 조합(Combination): 쌍(콤비) 만들기
- 부분집합(Subset): 가능한 모든 부분집합
가짓 수 계산
1)순열
nPr = n x (n-1) x ... x (n-r+1) = n! / (n-r)!
ex)4P2 = 4 x 3 = 12
2)조합
nCr = nPr / r!
ex)4C2 = 4P2 / 2! = 12 / 2 = 6
3)부분집합
n개 원소에 대한 부분집합 수 = 2n :공집합도 포함되어 있는 가짓 수임
ex)4개 원소에 대한 부분집합 수 = 24 = 16
코딩
프로그램에서, 원소가 주어지고 순열/조합/부분집합에 대한 경우의 수를 모두 표현하는 것은, Brute-Force에 해당하고, 이것을 코딩하는 것은예상보다 어렵다.
어떻게 코딩이 되는 지 각각 자세히 알아보자.
----------------------------------------------------------------------
1. 순열(Permutation)
순열(Permutation)은, 원소들에 대해서 한 줄로 세우는 방법을 말한다.(중복하지 않고)
예를 들어 {a,b,c,d}일 때, 2개를 뽑아서 일렬로 세우는 방법은 12가지
ab ac ad
ba bc bd
ca cb cd
da db dc
n개의 모든 원소에 대해 줄을 세우는 방법은 n!
프로그램은, 3가지 방법
1)단순 무식하게 중첩루프 사용
2)C++에 있는 next_permutation 함수 사용
3)재귀호출 사용해서 구현
방법1. 중첩루프 사용 (n개라면 n중첩)
for(int i=0; ...)
for(int j=0;...)
if(j==i) continue;
for(int k=0;...
if(k==i || k==j) continue;
for(int s=0; ...)
if(s==i || s==j || s==k) continue;
print();
방법2. next_permutation함수 사용
#include <algorithm>
do{
print(arr)
}while(next_permutation(arr,arr+n);
방법3. 재귀호출 사용
void permu(int n, int r, int idx){
if (idx == r){
for (int i = 0; i < r; ++i) printf("%c ", buf[i]);
printf("\n");
}
for (int i = 0; i < n; ++i){
if (used[i]) continue;
used[i] = 1;
buf[idx] = str[i];
permu(n, r, idx + 1);
used[i] = 0;
}
}
* next_permutation함수 제작
주어진 순열에 대해 다음번 순열이 무엇인지를 찾아내는 함수를 직접 제작해 본다. 알고리즘은 다음과 같다.
1) a[i-1]<a[i]인 최대 i를 찾아낸다. (i=n-1부터 왼쪽으로 가면서 찾는다.)
만약 i==0이면 다음 순열 없음 (이미 제일 마지막에 해당하는 순열임)
2) i<=j, a[i-1]<a[j]인 최대j를 찾는다.
3) swap(a[i-1], a[j])
4) j에서 끝까지에 있는 값들을 역순으로 바꾼다.
위 알고리즘은, {1,2,3,4}에 대한 순열을 차례대로 나열해가면서 위의 알고리즘을 음미하면 이해가 될 수 있다.
1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
// 여기서 다음 순서를 위 알고리즘으로 생각해보면,
// 1)a[i-1]=3, a[i]=4 ==> i-1=1, i=2
// 2)a[j]=4 ==> j=2
// 3)swap(3,4) ==> 1,4,3,2
// 4)j부터 끝까지를 역으로 놓으면 ==> 1,4, 2, 3
소스는 다음과 같다.
#include <stdio.h>int p[10001];bool next(int *a, int n){ int i,j; //1. find a[i-1]<a[i]인 최대i i = n-1; while(i>0 && a[i-1] >= a[i]) i--; if(i==0) return false; //2. i<=j, a[i-1]<a[j]인 최대j j=n-1; while(a[i-1]>=a[j]) j--; //j>0 조건불필요 //3. swap(a[i-1],a[j] int tmp=a[i-1]; a[i-1]=a[j]; a[j]=tmp; //4. reverse(a[i]...a[n-1]) j=n-1; while(i<j){ tmp = a[i]; a[i]=a[j]; a[j]=tmp; i++; j--; } return true;}2. 조합(Combination)
조합은 n개의 수 중에서 r개를 뽑아내어 집합을 만드는 방법을 말함. nCr 개 가짓수
3가지 구현 방법
1)단순 무식하게 중첩 루프 사용
2)재귀호출
3)순열 이용
{a,b,c,d}에 대해 2개씩 쌍을 만드시오.
==> ab ac ad bc bd cd
방법1. 중첩 루프 사용
for(int i=0;i<n;++i)
for(j=i+1;j<n;++j)
방법2. 재귀호출 사용
void combi(int n, int r, int s, int idx) {
if (idx == r){
for (int i = 0; i < r; ++i) printf("%c ",buf[i]);
printf("\n");
}
for (int i = s; i < n; ++i){
buf[idx] = str[i];
combi(n, r, i + 1, idx + 1);
}
}
방법3. 순열 이용
5개중 3개를 뽑아내어 집합을 만드는 조합은,
- 먼저 5개의 원소에 대해 3개는 1을, 나머지 2개는 0으로 놓은 후, 이 5개의 원소에 대한 순열 5P5=5!에 대한 경우를 뽑아낸다.
- 이 경우 중, 0의 경우는 무시하고, 1 원소에 대한 경우만을 고려하면, 이것이 순열에 대한 경우가 됨
3. 부분집합
부분집합은, 원소들에 대한 모든 부분집합을 구하는 것이다.
n개의 원소에 대한 부분집합 개수는 2n. 따라서 원소의 개수가 늘어날 수록 가짓 수는 지수적으로 늘어난다.
프로그램 구현방법은 2가지.
1)단순 무식하게 중첩루프
2)바이너리 카운팅
3)재귀 호출
방법1. 중첩루프 이용
for(i1 = 0; i1<2; ++i1)
bit[0]=i1;
for(i2=0; i2<2; ++i2)
bit[1]=i2;
for(i3=0;i3<2; ++i3)
bit[2]=i3;
print(bit);
방법2. 바이너리 카운팅 이용
for(int i=0; i < (i << (n)); ++i){
for(int j=0;j<n;++j){
if (i & (1<<j))
printf("%d, ", arr[j]);
}
printf("\n");
}
방법3. 재귀호출 이용
int flag[N];
void powerset(int n, int depth){
if (depth == n){
for (int i = 0; i < n; ++i) if (flag[i]) printf("%c ",str[i]);
printf("\n");
return;
}
flag[depth] = 1;
powerset(n, depth + 1);
flag[depth] = 0;
powerset(n, depth + 1);
}
-끝-