순열( permutation )이란?

• 순열( permutation )이란 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산을 말합니다. (1, 2, 3) 이렇게 있을 때 (1, 3, 2) 이런식으로 다른 순서로 섞는 연산을 순열이라고 합니다. 그리고 n개의 집합 중 n개를 고르는 순열의 개수는 n!이라는 특징을 가지고 있습니다.
  예를 들어 3개의 자연수 (1, 2, 3)을 이용해 만들 수 있는 3자리 자연수는 123, 132, 213, 231, 312, 321 이렇게 6개 입니다. 그렇다면 3개의 자연수 (1, 2, 3)을 이용해 만들 수 있는 1자리 자연수는 몇개일까요? 바로 1, 2, 3 총 3입니다.

순열 경우의 수 공식

• n!/(n-r(선택할 숫자의 개수))!

next_permutation과 prev_permutation

• C++은 순열을 구현한 next_permutation과 prev_permutation 함수를 제공하며 해당 함수를 사용하려면 algorithm을 include 해야합니다.

next_permutation

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

using namespace std;

int main()
{
    vector<int> vec = { 1,2,3 };

    do
    {
        for (auto value : vec) {
            cout << value;
        }

        cout << endl;

    } while (next_permutation(vec.begin(), vec.end()));

    return 1;
}

• next_permutation은 오름 차순으로 정렬된 vector를 기준으로 순열 알고리즘을 제공합니다. 또한 범위를 지정하여 순열 알고리즘을 사용할 범위를 지정할 수 있습니다.

prev_permutation

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

using namespace std;

int main()
{
    vector<int> vec = { 3,2,1 };

    do
    {
        for (auto value : vec) {
            cout << value;
        }

        cout << endl;

    } while (prev_permutation(vec.begin(), vec.end()));

    return 1;
}

• prev_permutation은 내림 차순으로 정렬된 vector를 기준으로 순열 알고리즘을 제공합니다. 도한 범위를 지정하여 순열 알고리즘을 사용할 범위를 지정할 수 있습니다.

재귀를 이용한 순열

#include <iostream>
#include <vector>

using namespace std;

void makePermutation(int cnt, int depth, vector<int>& arr) {
    if (cnt == depth) {
        for (auto v : arr) {
            cout << v << " ";
        }
        cout << endl;
    }

    for (int i = cnt; i < arr.size(); ++i) {
        swap(arr[cnt], arr[i]);
        makePermutation(cnt + 1, depth, arr);
        swap(arr[cnt], arr[i]);
    }
    return;
}

int main()
{
    vector<int> vec = { 1,2,3,4 };

    makePermutation(0, 4, vec);

    return 1;
}

• next_permutation, prev_permutation을 사용하지 않고 순열을 위와같이 구현 가능합니다.