C++ 순열,조합 알고리즘(next_permutation)

생각보다 자주 나오고 알아두면 유용한 next_permutation에 대해 정리해보려고 한다.
(알고 있지만, 자꾸 사용법을 까먹어서 정리해야겠다🧐)

순열

수학적으로 순열(permutation)이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다. 원소를 한 줄로 세우기 때문에 원소의 조합이 같더라도 순서가 다르면 다른 방법으로 봅니다.

예를 들어 집합 {1, 2, 3}의 원소들의 모든 순열을 구한다면
{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
로 총 6가지가 나오게 됩니다.

next_permutation

#include <algorithm>
next_permutation(Arr.begin(), Arr.end());

👉🏻 next_permutation을 사용하려면 algorithm 헤더를 포함해줘야한다.
👉🏻 반복자를 이용하기 때문에 string,vector 등이 가능하다.
👉🏻 사용되는 벡터는 오름차순으로 정렬 되어있어야 한다.
(더 큰 순열을로 재배열을 할 수 있으면 반복하여 구해내는 구조이므로 앞에 이미 큰 원소들이 배치되어 있으면 반복하지 않게 된다.)
👉🏻 보통 do~while 이랑 같이 쓰인다.
이유는, 반복문을 돌다가 next_permutation을 만나면 다음 순열로 바꾼다.

int main() {
    int n;
    cin >> n;

    vector<int> v;

    for(int i = 1; i <= n; i++)
        v.push_back(i);

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

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

    return 0;
    
}

백준 10974의 풀이이며, 모든 순열 구하는 방법이다.

조합

next_permutation은 같은 방식으로 조합도 가능하다.

🧐조합이란?
n개의 원소를 갖는 집합에서 m(n 이하의 자연수)개를 선택하여 만드는 부분집합들이다.

k 개의 원소에 1을, n-k 개의 원소에 0을 넣어 만든 조합을 만들어, 원소가 1인 인덱스에 해당하는 값을 가져오면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n = 6;
    int k = 4;
 
    vector<int> v;
 
    for (int i = 1; i <=n; i++)
    {
        v.push_back(i);
    }
 
    // 0, 1을 넣어 임시 조합 생성
    vector<int> tempVector;
 
    for (int i = 0; i < k; i++)
    {
        tempVector.push_back(1);
    }
 
    for (int i = 0; i < v.size() - k; i++)
    {
        tempVector.push_back(0);
    }
 
    sort(tempVector.begin(), tempVector.end());
 
    do
    {
        for (int i = 0; i < tempVector.size(); i++)
        {
            if (tempVector[i] == 1)
            { // 실제값 출력
                cout << v[i] << " ";
            }
        }
 
        cout << endl;
 
    } while (next_permutation(tempVector.begin(), tempVector.end()));
 
    return 0;
}

👉🏻여기서 tempVector은 임시 벡터로, 처음에는 구하고자 하는 K개 만큼 1을 넣고 나머지는 0을 넣어준다.
그 후, temp벡터를 이용하여 next_permutation을 진행한다. 반복문을 돌면서 temp[i]가 1인 경우에 실제값이 들어있는 원래의 벡터의 출력해준다.