순열, 조합, 중복순열, 중복조합 - 코드

순열

서로 다른 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부터

시간복잡도의 경우 해당 탐색의 경우의 수와 동일하다.