해당 포스팅에는 배열과 숫자를 나눠서 탐색하는 방법을 적겠습니다.
목차
- 1. power set, 멱집합
- 2. Permutation with repeatation
- 3.Permutation
- 4. Combination
- 5. Combination with repeatation
- 6. Partition of natural number
- Partition of set
1. power set, 멱집합
멱집합은 해당 집합의 부분집합들의 집합입니다.
1
int arr[5] = {0,1,2,3,4} // 다른 숫자로 써도 됩니다. arr에 index로 접근하면 되기 때문입니다.
1.1 positional notation, 위치 기수법
- 시간 복잡도 $O(N 2^N)$
- 공간 복잡도 $O(1)$
example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void superSetByPlaceNumber(int arr[], int n){
int power_set_size = 1;
for(int i = 0; i <n; i++) power_set_size *= 2;
// becuase double has 15 significant number. if we use pow, there whould be error.
for(int counter = 0; counter < power_set_size; counter++){
for(int place_number = 0; place_number < n; place_number++){
if(counter&(1 << place_number))
cout << arr[place_number];
}
cout << "\n";
}
}
1.2 Back tracking
장점 : 단순 arr의 선택이 아닌 복잡한 2D 좌표간의 이동도 나타낼 수 있습니다.
1~N개의 combination을 돌리면 된다.
- 시간 복잡도 $O(N 2^N)$
- 공간 복잡도 $O(N)$ example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> picked;
void superSetByBackTracking(int m, int n){
if(picked.size() == n){
for(int i : picked)
cout << i << " ";
cout << "\n";
return;
}
int smallest = picked.empty()? 0 : picked.back()+1;
for(int i = smallest; i < m; i++){
picked.push_back(i);
superSetByBackTracking(m,n);
picked.pop_back();
}
int main(){
for(int i = 0; i <= 5; i++)
superSetByBackTracking(sizeof(arr)/sizeof(int), i);
}
1.3 lexicographical order 사전순 구현
n개의 선택하는 원소와 next_permutation을 통해 나타낸다.
- 시간 복잡도 $O(N logN+ N 2^N)$
- 공간 복잡도 $O(N)$
example1 2
//step1 sorting : 오름차순 정렬 됩니다. //step2 next permutation : 다음 내림차순으로 원소를 바꿉니다.
2. Permutation with repeatation
서로 같은 것을 서로 다른 것에 분할 하는 방입니다.
2.1 back tracking 구현
- 시간 복잡도 $O(N^M)$
- 공간 복잡도 $O(N)$
example1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
void permutationWithRepeatation(int arr[], int to_pick){ // 인수로 total을 넘기면서 search도 가능. 하지만 무엇을 뽑았는지는 저장 안 됨. if(picked.size() == to_pick){ for(int i : picked) cout << i << " "; cout << "\n"; return; } for(int i = 0; i < 5; i++){ picked.push_back(i); permutationWithRepeatation(arr,to_pick); picked.pop_back(); } }
2.2 positional notation
n진법을 쓰면 0~n-1 숫자로 이루어진 집함을 만들 수 있습니다.
- 시간 복잡도 $O(N^M)$
- 공간 복잡도 $O(1)$ example
1
2
3
4
5
6
7
8
9
10
11
12
13
void permutationWithRepeatation2(int n, int m ){ // 인수로 total을 넘기면서 search도 가능.
long long count = 1;
for(int i = 0; i < m; i++) count *= n;
while(count--){
long long tmp = count;
for(int place_num = 0; place_num < m; place_num++){
cout << tmp % n;
tmp /= n;
}
cout << "\n";
}
}
3.Permutation
- 시간 복잡도 $O(N * N!) $
- 공간 복잡도 $O(N)$
3.1 lexicographical 사전순으로 구현
사전순으로 구현할 시, nPn만 구할 수 있다.
example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Permutation(int n, int m){
vector<int> increase(m);
for(int i = 0; i<m; i++) increase[i]= i;
do{
for(int i : increase)
cout << i << " ";
cout << "\n";
}while(next_permutation(increase.begin(), increase.end()));
}
int main(){
Permutation(5,3); // 5개 중에서 순서를 고려해서 3개 뽑을 수 없음.
//5개중에 5개 모두 뽑거나, 3개중에 3개 모두 뽑아야 함.
}
3.2 back tracking
만약 nPm을 구하고 싶다면 back tracking으로 직접 구현해야 한다.
example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool is_used[5];
void backPermut(int n, int m){
if(picked.size() == m){
for(int i: picked)
cout << i << " ";
cout << "\n";
}
for(int i = 0; i < n; i++){
if(is_used[i]) continue;
is_used[i] = true;
picked.push_back(i);
backPermut(n,m);
is_used[i] = false;
picked.pop_back();
}
}
int main(){
backPermut(5,3);
}
4. Combination
순서를 강제해서 뽑는다고 생각하면 됩니다.
- 시간 복잡도 $O(min(n^k, n^(n-k)))$
- 공간 복잡도 $O(N)$
4.1 lexicographical
1
2
//next_permutation에 같은 원소를 넣어서 구현한다.
// 가령 0 0 0 0 1 1 은 5C2입니다.
4.2 choose smallest in the array. using vector STL
example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void print_combination(int n, int m){
if(picked.size() == m){
for(int elem: picked)
cout << elem << " ";
cout << "\n";
return;
}
// 내림 차순 정렬 후, 안 쓰는 smallest indx 반환하는 것이 중요.
int smallest = picked.empty() ? 1 : picked.back()+1;
//smalllest부터 돌음
for(int i = smallest; i <= n; i++){
picked.push_back(i);
print_combination(n, m);
picked.pop_back();
}
}
5. Combination with repeatation
서로 다른 것을 서로 같은 곳에 분할 하는 방법.
- 시간 복잡도 $O(n+r-1Cr)$
- 공간 복잡도 $O(N)$
example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int N, M;
vector<int> chosen;
void Homogenious(int n, int m){
if(chosen.size() == m){
for(int i: chosen)
cout << i+1 << " ";
cout << "\n";
return;
}
int smallest = chosen.empty() ? 0 : chosen.back();
for(int i = smallest; i < n; i++){
chosen.push_back(i);
Homogenious(n, m);
chosen.pop_back();
}
}
6. Partition of natural number
서로 같은 것을 서로 같은 것에 분할 하는 방법입니다.
$P(n,m)$ : n을 m 이하의 자연수들의 합으로 나타내는 방법
$P[n][m] = \displaystyle \sum_{i=1}^m D[n-i][i] $
이때 각각의 i는 집합을 분할 했을 때 사용한 최대 수입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
//https://blankspace-dev.tistory.com/73에 나와있습니다.
int partition(int n, int m){
if(n < m)
m = n;
if(n == 0)
return 1;
int cnt = 0;
for(int i = 1; i <= m; i++)
cnt += partition(n-i, i);
return cnt;
}
Partition of set
서로 같은 것을 서로 다른 것으로 분할 하는 방법입니다.
수학에서는 자연수의 분할을 시행한 후, combination으로 중복 처리를 해주면 됩니다.
하지만 프로그래밍 에선 -> power set 만드는 것과 동일합니다.
Comments