DFS로 조합, 순열 만들기

 

 

재귀로 조합을 만들 때 핵심은 시작점과 레벨이다.

• 시작점부터 for문을 돌며 현재 레벨에 하나씩 찍어보고, 다음 시작점과 레벨 + 1을 전달해 탐색을 계속한다.

 

또한 앞에서 뒷방향으로 진행하며 앞의 내용을 유지해야하므로, 탐색에서 같은 결과 배열을 사용한다.

 

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

void rCombination(int start, int depth, vector<int>& comb, vector<int>& v)
{
    if (comb.size() <= depth)
    {
        print(comb);
        return;
    }

    for (int i = start; i < v.size(); ++i)
    {
        comb[depth] = v[i];
        rCombination(i + 1, depth + 1, comb, v);
    }
}

void main()
{
    int n = 5, r = 3;

    vector<int> v(n), comb(r);

    iota(v.begin(), v.end(), 1);

    rCombination(0, 0, comb, v);
}

 

출력

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

 

 

재귀로 순열을 만들 때 핵심은 레벨과 사용 중 배열이다.

• 인덱스 0부터 for문을 돌며 사용 중이 아니면, 현재 레벨에 하나씩 찍어본다.
  사용 중 배열을 관리하며 매번 0부터 도는 이유는, (3, 1) 이후에 (1, 3)도 확인해야 하기 때문이다.
• 이후 사용 중 배열에 현재 원소를 표시하고, 레벨 + 1을 전달해 탐색을 계속한다.
• 현재 원소에서 탐색이 끝난 후에는 다시 사용 중이 아님으로 표시해준다.

 

또한 앞에서 뒷방향으로 진행하며 앞의 내용을 유지해야하므로, 탐색에서 같은 결과 배열을 사용한다.

 

(시작점, 레벨)핵심인 조합과 달리, 순열은 (레벨, 사용 중 배열)이 핵심이다.

 

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

void rPermutation(int depth, vector<bool>& inUse, vector<int>& perm, vector<int>& v)
{
    if (perm.size() <= depth)
    {
        print(perm);
        return;
    }

    for (int i = 0; i < v.size(); ++i)
    {
        if (inUse[i] == false)
        {
            inUse[i] = true;
            perm[depth] = v[i];
            rPermutation(depth + 1, inUse, perm, v);
            inUse[i] = false;
        }
    }
}

void main()
{
    int n = 4, r = 3;

    vector<int> v(n), perm(r);
    vector<bool> inUse(n, false);

    iota(v.begin(), v.end(), 1);

    rPermutation(0, inUse, perm, v);
}

 

출력

1 2 3
1 2 4
1 3 2
1 3 4
1 4 2
1 4 3
2 1 3
2 1 4
2 3 1
2 3 4
2 4 1
2 4 3
3 1 2
3 1 4
3 2 1
3 2 4
3 4 1
3 4 2
4 1 2
4 1 3
4 2 1
4 2 3
4 3 1
4 3 2