DFS - 조합과 순열

조합과 순열

조합

• nCr (조합)
• 조합은 순서가 상관이 없는 모임을 의미한다.
• 순서가 상관 없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은 것으로 취급을 한다. 
• (3, 6, 9)에서 숫자 2개로 구성된 조합을 구한다면
  -> (3, 6), (3, 9), (6, 9)  

순열

• nPr (순열)
• 순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 의미한다. 즉 순서가 존재함을 의미한다
• 즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 은 모두 다른 결과를 가져온다.
• (3, 6, 9)에서 숫자 2개로 구성된 순열을 구한다면
  -> (3, 6), (3, 9), (6, 3), (6, 9), (9, 3), (9, 6)  

 

DFS로 구현

DFS를 사용하여 5가지 숫자중에서 3개의 숫자로 된 조합과 순열을 구해보았다.

조합

#include <iostream>
using namespace std;

//5개의 숫자중에서 3개의 숫자로 된 조합 구하기

bool visited[5];
vector<int> v; // 조합을 담을 벡터

// 1 2 3 의 형태로 출력
void print() {
    for (int i = 0; i < 5; i++) {
        if (visited[i] == true)
            cout << arr[i] << ' ';
    }
    cout << '\n';
}
 
void dfs(int idx, int cnt) {
    if (cnt == 3) {
    	print();
        return;
    }
 
    for (int i = idx; i < 5; i++) {
        if (!visited[i]){
            visited[i] = true;
            dfs(i, cnt++);
            visited[i] = false;
        }
    }
}
int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    dfs(0, 0);

    return 0;
}

 for (int i = idx; i < 5; i++) { } 처럼, idx를 받아 그 위치부터 반복문을 돌면 순서가 없는 조합을 구할 수 있다.

 

순열

#include <vector>
using namespace std;

bool visited[5];
vector<int> v;

void print() {
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << ' ';
    cout << '\n';
}

void dfs(int cnt) {
    if (cnt == 3) {
        print();
        return;
    }
    for (int i = 0; i < 5; i++) {
        if (!visited[i]){
        visited[i] = true;
        v.push_back(arr[i]);
        dfs(cnt++);
        v.pop_back();
        visited[i] = false;
        }
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    dfs(0);
    return 0;
}

 

 

---

https://foameraserblue.tistory.com/62

조합과 순열 c++ 로 구현