순열, 조합, 중복순열, 중복조합 with C++

1. 순열(Permutation)

순서를 따지고, 중복을 허용하지 않는다. (순서O, 중복X)

백준 관련 문제 : 모든 순열

-> 백트랙킹 문제, visit 배열을 둬 중복을 검사한다. 재귀를 이용해 다른 원소에 대해 똑같이 수행한다.

 

c++ 코드 :

//
//  10974_all_ permutation.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/27.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>


using namespace std;
vector<int> v;
bool visit[9];
int n;

///<algorithm> -> next_permutation(순열 시작, 순열 끝)
/// with recursive 
void make_permu_dfs(){
    if(v.size() == n){
        for(int i = 0; i < n; i++){
            cout << v.at(i) << " ";
        }
        cout << endl;
        return;
    }else{
        for(int i = 1; i <= n; i++){
            if(visit[i] == false){
                visit[i] = true;
                v.push_back(i);
                make_permu_dfs();
                v.pop_back();
                visit[i] = false;
            }
        }
    }
}

int main(){
    cin >> n;
    memset(visit, false, sizeof(visit));
    make_permu_dfs();
    return 0;
}

 

2. 조합(Combination)

주머니에서 공을 여러개 뽑는것과 같다. 순열과 다르게 순서는 중요하지 않다.

백준 관련 문제 : N과M(1)

-> 순열과 마찬가지로 visit 배열을 둬 중복을 검사한다. 현재 원소 집합에 해당 원소가 있다면 건너뛴다. (set을 사용해도 될거 같다)

 

c++ 코드 :

//
//  15649_N&M.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/09/10.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N, M;
vector<int> v;
int visit[9] = { false, };
vector<int>::iterator it;

//combination
void make_dfs(){
    if(v.size() == M){
        for(int i = 0; i < M; i++){
            cout << v[i] << " ";
        }
        cout << '\n';
        return;
    }else {
        for(int j = 1; j <= N; j++){
            if(visit[j] == false){
                if(find(v.begin(), v.end(), j) != v.end()) { continue; }
                visit[j] = true;
                v.push_back(j);
                make_dfs();
                v.pop_back();
                visit[j] = false;
            }
        }
    }
}

int main(){
    cin >> N >> M;
    make_dfs();
    return 0;
}

 

3. 중복 순열

순서가 있는 수열에서 원소 중복을 허용한다.

백준 관련 문제 : N과M(3)

-> 중복을 허용하므로 따로 visit 배열을 두지 않는다.

 

c++ 코드 :

//
//  15651_N&M(3).cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/02/20.
//

#include <iostream>

using namespace std;
int N, M;
int arr[8];
//중복 순열
void backTracking(int cnt){
    if(cnt == M){ // M개 다 골랐다면
        for(int i = 0; i < M; i++){
            cout << arr[i] << ' ';
        }
        cout << '\n';
        return;
    }
    
    for(int i = 1; i <= N; i++){
        arr[cnt] = i;
        backTracking(cnt+1);
    }
}

int main(){
    cin >> N >> M;
    backTracking(0);
    return 0;
}

 

4. 중복 조합

중복해서 같은 원소를 뽑을 수 있다.

백준 관련 문제 : N과M(4)

-> 중복 순열과 다르게 num 매개변수를 둬서 이전에 시작한 원소부터 다시 재귀를 호출한다.

 

c++ 코드 :

//
//  15652_N&M(4).cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/02/20.
//

#include <iostream>

using namespace std;
int N, M;
int arr[8];

//중복 허용 + 증가하는 순
void backTracking(int cnt, int num){
    if(cnt == M){
        //출력
        for(int i =0; i < M; i++){
            cout << arr[i] << " ";
        }
        cout << '\n';
        return;
    }
    
    for(int i = num; i <= N; i++){
        arr[cnt] = i;
        backTracking(cnt + 1, i); // num, i 차이
    }

}

int main(){
    cin >> N >> M;
    backTracking(0, 1);
    return 0;
}