순열, 조합 알고리즘 - DFS로 구하기(백트래킹), C++, Python

순열, 조합은 정말정말 많이 나오는데 cpp의 stl 라이브러리 중 next_permutation으로 구할 수 있다.

하지만 next_permutation은 N이 20만 넘어가도 터질 위험에 처한다.. 시간복잡도가 크기 때문이다. N이 10 언저리일때 쓰면 좋다.

재귀를 사용하여 DFS탐색을 통해 순열, 조합을 구하는 것이 가장 안전하고 깔끔하다.

순열 구하기

#include<iostream>
#include<string.h>
#include<vector>
#define MAX 5
using namespace std;
vector<int>arr;
vector<int>result;
int visit[MAX];

/* 순열 구하기 */
void prt_permu() {
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << ' ';
    }
    cout << endl;
}
void dfs_permu(int cnt){
    if (cnt == 3) { // 찾으려는 개수 
        prt_permu();
        return;
    }
    for (int i = 0; i < MAX; i++) {
        if (visit[i] == true) continue;
        visit[i] = true;
        result.push_back(arr[i]);
        dfs_permu(cnt + 1);
        result.pop_back();
        visit[i] = false;

    }
}

int main() {
    for (int i = 0; i <MAX; i++) {
        arr.push_back(i+1);
    }
    dfs_permu(0);
 }
     /*
    1 2 3
    1 2 4
    1 2 5
    1 3 2
    1 3 4
    1 3 5
    1 4 2
    1 4 3
    1 4 5
    1 5 2
    1 5 3
    1 5 4
    2 1 3
    2 1 4
    2 1 5
    2 3 1
    2 3 4
    2 3 5
    .
    .
    .
    */

조합 구하기

#include<iostream>
#include<string.h>
#include<vector>
#define MAX 5
using namespace std;
vector<int>arr;
vector<int>result;
int visit[MAX];

/* 조합 구하기 */
void prt_combi() {
    for (int i = 0; i < MAX; i++) {
        if (visit[i] == true) {
            cout << arr[i] << ' ';
        }
    }
    cout << endl;
}
void dfs_combi(int idx, int cnt) {
    if (cnt == 3) {
        prt_combi();
        return;
    }
    for (int i = idx; i < MAX; i++) {
        if (visit[i] == true) continue;
        visit[i] = true;
        dfs_combi(i, cnt + 1);
        visit[i] = false;
    }
}


int main() {
    for (int i = 0; i <MAX; i++) {
        arr.push_back(i+1);
    }
    dfs_combi(0, 0);
    /*
    1 2 3
    1 2 4
    1 2 5
    1 3 4
    1 3 5
    1 4 5
    2 3 4
    2 3 5
    2 4 5
    3 4 5
    */
}

Python으로 구한다면 아래와 같다.

순열

• itertools

    from itertools import permutations, combinations
    data = ['a', 'b', 'c']
    result = list(permutations(data, 3)) 
    print(result)
  
    #[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

• backtracking

    def dfs(level):
        if level == r: # r개를 뽑은 경우
            print(result)
            return
        for i in range(len(n)):
            if checked[i] == True: continue
            result[level] = n[i]
            checked[i] = True
            dfs(level+1)
            checked[i] = False       
  
    n = [i+1 for i in range(3)]
    r = 2 # r개 뽑기
    result = [0] * r
    checked = [False] * len(n)
    dfs(0)
    #   [1, 2]
    #   [1, 3]
    #   [2, 1]
    #   [2, 3]
    #   [3, 1]
    #   [3, 2]

조합

• itertools

    from itertools import permutations, combinations
    data = ['a', 'b', 'c']
    result = list(combinations(data, 2)) # 조합
    print(result)
  
    #[('a', 'b'), ('a', 'c'), ('b', 'c')]

• backtracking

    def dfs(level, BeginWith):
        if level == r: # r개를 뽑은 경우
            print(result)
            return
        for i in range(BeginWith, len(n)):
            result[level] = n[i]
            dfs(level+1, i+1)       
  
    n = [i for i in range(10)]
    r = 6 # r개 뽑기
    result = [0] * r
    dfs(0, 0)
  
    #   [1, 2, 3]
    #   [1, 2, 4]
    #   [1, 2, 5]
    #   [1, 3, 4]
    #   [1, 3, 5]
    #   [1, 4, 5]
    #   [2, 3, 4]
    #   [2, 3, 5]
    #   [2, 4, 5]
    #   [3, 4, 5]

중복순열

• itertools

    from itertools import product
  
    n = [i+1 for i in range(3)]
    r = 2
  
    result = list(product(n, repeat=r)) 
  
    print(result)
    # [
    #   (1, 1), (1, 2), (1, 3), 
    #   (2, 1), (2, 2), (2, 3), 
    #   (3, 1), (3, 2), (3, 3)
    # ]

• backtracking

    def dfs(count):
    if count == m:
        print(*result)
        return
    for i in range(1,n+1):
        result.append(i)
        dfs(count+1)
        result.pop()
  
    dfs(0)

중복조합

• itertools

    from itertools import combinations_with_replacement
  
    n = [i+1 for i in range(3)]
    r = 2
  
    result = list(combinations_with_replacement(n, r))  # 중복조합에서는 repeat가 안들어간다.
  
    print(result)
    # [
    #   (1, 1), (1, 2), (1, 3), 
    #   (2, 2), (2, 3), 
    #   (3, 3)
    #    ] 

• backtracking

    result = []
    def dfs(idx, count):
        if count == m:
            print(*result)
            return
        for i in range(idx, n):
            result.append(i+1)
            dfs(i, count+1)
            result.pop()
  
    dfs(0, 0)