순열 / 조합

순열과 조합

어떤 수를 순서에 관계있이 뽑는다면 -> 순열

어떤 수를 순서와 관계없이 뽑는다면 -> 조합

 

C++에서는 순열을 위해 <algorithm>헤더에서 next_permutation 함수를  제공한다 

next_permutation은 오름차순으로 순열을 만든다. prev_permutation은 내림차순

인자는 시작과 끝 이터레이터이다.

next_permutation(v.begin(), v.end());

 

vector<int> v = {1, 2, 3}
do{
	for(int i : a) cout << i << " ";
    cout << endl;
}while(next_permutation(a.begin(), a.end()));

 

위 결과는

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

로 나온다.

그러나 오름차순 정렬되어있지 않다면

{2, 1, 3} 으로 넘기면 

2 1 3

2 3 1

3 1 2

3 2 1

로 출력된다. 다음의 수를 추출하는 것 뿐.

따라서 순열 사용 전에 반드시 sort(v.begin(), v.end()) 를 진행하자.

 

[ 공식 ]

n 개중에 r개를 뽑는다.

3개중에 2개를 뽑는 경우는 3! / (3-2)! 라서 3!이 나온다.

 

순열 직접 구현

구현은 생각보다 간단한 편.

#include <iostream>
#include <vector>

using namespace std;
void makePermutation(vector<int>& v, int depth);

int n = 3;
int m = 3;

int main()
{
    vector<int>* v = new vector<int>{ 1, 2, 3 };

    makePermutation(*v, 0);
    return 0;
}

void makePermutation(vector<int>& v, int depth)
{
    if (depth == m)
    {
        for (const int& i : v)
        {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = depth; i < n; ++i)
    {
        swap(v[i], v[depth]);
        makePermutation(v, depth + 1);
        swap(v[i], v[depth]);
    }
}

 

do while 로 구현하면 다음과 같다.

algorithm 헤더에 있는 next_permutation 을 사용하자.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int>* v = new vector<int>{ 1, 2, 3 };

    do
    {
        for (const int& i : *v)
        {
            cout << i << " ";
        }
        cout << "\n";
    } while (next_permutation(v->begin(), v->end()));
    return 0;
}

 

 

조합

조합은 순서 상관없이 뽑는 갯수를 말한다.

 

[ 공식 ]

n 개 중에 r 개를 뽑는데, 순서는 상관이 없다.

5라면 10이 나온다!

 

재귀함수는 4개 이상 뽑는건 재귀가 편하다. 

3개 이하는 중첩이 편하다.

 

재귀로 구현한 조합

vector가 빈 상태로 시작하고

시작인덱스는 -1부터 시작하는 것에 주의.

 

이제 인덱스를 얻어냈으니, 가지고 있던 컨테이너에서 인덱스를 기반으로 뽑아내면 편하다.

#include <iostream>
#include <vector>

using namespace std;
void combi(vector<int>& v, int start);

int _n = 5;
int _maxLength = 3;

int main()
{
    vector<int> v;
    combi(v, -1);
    return 0;
}

void combi(vector<int>& v, int start)
{
    if (v.size() == _maxLength)
    {
        for (const int& i : v)
        {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = start + 1; i < _n; ++i)
    {
        v.push_back(i);
        combi(v, i);
        v.pop_back();
    }
}

 

갯수만 필요한 경우라면 아래와 같이 구현한다.

int combination(int n, int r)
{
    if (n == r || r == 0) 
        return 1; 
    else 
        return combination(n - 1, r - 1) + combination(n - 1, r);
}

 

중첩 for문을 사용하는 방법

- 쉽고 편하지만 우아하지는 않은 듯.

#include <iostream>
#include <vector>

using namespace std;
int n = 5;
int k = 3;
int a[5] = { 1, 2, 3, 4, 5 };

int main() {
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            for (int k = 0; k < j; k++)
            {
                cout << i << " " << j << " " << k << "\n";
            }
        }
    }
    return 0;
}