순열, 조합, 중복순열, 중복조합 - 코드
순열
서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하지 않고", "뽑는 순서를 고려하는" 것
1. DFS로 탐색 : O(nPr)
다만 이 경우는 중복이 있는 경우는 못 잡는다!
// nPr의 경우
// arr : 순열할 원소, size n
// visited[i] : arr[i]가 방문되었는지 여부, 초기값 false, size n
// result : 순열 결과, size r
void permutation(int depth, int r, vector<int>& arr, vector<bool>& visited, vector<int>& result){
if(depth == r){
for(int i : result){
cout<<i<<" ";
}cout<<endl;
return;
}
for(int i = 0; i<arr.size(); i++){
if(!visited[i]){ // 사용된 것이라면 사용하면 안됨
visited[i] = true;
result[depth] = arr[i];
permutation(depth+1, r, arr, visited, result);
visited[i] = false;
}
}
}
2. STL 이용 : O(n!)
순열은 next_permutation이라는 STL이 존재한다. 이 STL을 사용하는 것이 좀 더 편하긴 할 것이다. 다만 유의할 점이 있다. 전체를 나열시키는 경우를 제외하고는 backtracking으로 계산하는 것이 더 낫지 싶다.
- arr은 오름차순 정렬되어 있어야 한다.
- n개를 순서대로 나열시키는 경우밖에 하지 못한다.
- nPr을 하기 위해서는 arr 전체 출력이 아닌, arr에서 앞에서부터 r개만 출력하면 된다.
// arr : 순열할 원소, size n
void permutation2(vector<int>& arr){
sort(arr.begin(), arr.end());
do{
for(int i : arr){
cout<<i<<" ";
}cout<<endl;
}while(next_permutation(arr.begin(), arr.end()));
}
* 중복이 있는 경우도 생각해야 할 수 있다.
조합
서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하지 않고", "뽑는 순서를 고려하지 않는" 것이 조합이다.
1. DFS로 탐색 : O(nCr)
이전에 뽑은 원소는 사용하면 안되므로 이전에 뽑은 원소 다음 것(반복문 시작 값을 유의해야 한다)부터 사용한다.
// nCr의 경우
// arr : 조합할 원소, size n
// result : 조합 결과, size r
void combination(int depth, int r, int prev_idx, vector<int>& arr, vector<int>& result){
if(depth == r){
for(int i : result){
cout<<i<<" ";
}cout<<endl;
return;
}
for(int i = prev_idx; i<arr.size(); i++){
result[depth] = arr[i];
combination(depth+1, r, i+1, arr, result);
}
}
2. STL 이용
조합도 next_permutation을 이용해 풀 수 있다. 0과 1이 담긴 temp 배열을 순열시켜서 이것이 1인 것만 보는 것이다. 다만 temp 함수가 오름차순으로 정렬되어 있다면 조합이 내림차순으로 나온다.(1이 더 큰 수기 때문) 따라서 오름차순 조합이 필요하다면 위과 같이 사용하자.
// nCr, arr : 조합할 원소, size n
void combination1(int n, int r, vector<int>& arr){
vector<int> temp(n, 0);
for(int i = 0; i<r; i++){
temp[i] = true;
}
do{
for(int i = 0; i<n; i++){
if(temp[i]) cout<<arr[i]<<" ";
} cout<<endl;
}while(prev_permutation(temp.begin(), temp.end()));
}
void combination2(int n, int r, vector<int>& arr){
vector<int> temp(n, 0);
for(int i = n-r; i<n; i++){
temp[i] = true;
}
do{
for(int i = 0; i<n; i++){
if(temp[i]) cout<<arr[i]<<" ";
} cout<<endl;
}while(next_permutation(temp.begin(), temp.end()));
}
중복순열
서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하고", "뽑는 순서를 고려하는" 것이 중복순열이다.
1. DFS로 탐색 : O($n \Pi r$)
이전에 뽑은 원소에 신경쓰지 않고 탐색하면 되므로 쉽게 구현할 수 있다.
// nPIr의 경우
// arr : 순열할 원소, size n
// result : 순열 결과, size r
void duplicatePermutation(int depth, int r, vector<int>& arr, vector<int>& result){
if(depth == r){
for(int i : result){
cout<<i<<" ";
}cout<<endl;
return;
}
for(int i = 0; i<arr.size(); i++){
result[depth] = arr[i];
duplicatePermutation(depth+1, r, arr, result);
}
}
중복조합
서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하고", "뽑는 순서를 고려하지 않는" 것이 중복조합이다.
1. DFS로 탐색 : O(nHr)
이전에 뽑은 원소도 사용할 수 있으므로 이전에 뽑은 원소부터 재귀를 한다.(반복문 시작 값을 유의해야 한다)
// nHr의 경우
// arr : 조합할 원소, size n
// result : 조합 결과, size r
void duplicateCombination(int depth, int r, int prev_idx, vector<int>& arr, vector<int>& result){
if(depth == r){
for(int i : result){
cout<<i<<" ";
}cout<<endl;
return;
}
for(int i = prev_idx; i<arr.size(); i++){
result[depth] = arr[i];
duplicateCombination(depth+1, r, i, arr, result);
}
}
DFS로 탐색 시 요약
순열 : for문의 i는 depth에 상관없이 index 0부터, visited 사용 必
조합 : for문의 i는 이전 depth에서 뽑은 원소의 다음 index부터
중복순열 : for문의 i는 depth에 상관없이 index 0부터
중복조합 : for문의 i는 이전 depth에서 뽑은 원소의 index부터
시간복잡도의 경우 해당 탐색의 경우의 수와 동일하다.