[C++] [STL] next_permutation

순열과 조합은 알고리즘 문제 풀면서 사용되는 개념으로 많이 사용된다.

문제 난이도에 따라 순열/조합 구현만 요구할 수 있지만

[경우의 수  + α] 를 요구하는 문제가 많은 편이다.

 

순열(Permutation)이란 서로 다른 n개의 원소에서 r개 선택해서 줄을 세우는 것이다.

「줄을 세우는 것」은 순서에 따라 각기 다른 경우로 취급

cf. 조합(Combination)은 순서가 다르더라도 동일한 경우로 처리

 

ex) 원소가 3개인 집합 {1, 2, 3}에서 2개 뽑는 경우의 수

• 순열: {1, 2} {2, 1} {2, 3} {3, 2} {1, 3} {3, 1} →  3P2

• 조합: {1, 2} {2, 3} {1, 3} → 3C2

📌 순열과 조합

순열과 조합 (백준 N과 M 시리즈)

---

next_permutation()

C++ STL 중에서도 순열/조합을 쉽게 구현할 수 있게

next_permutation라는 것을 제공한다.

• 헤더파일 #include <algorithm>

• 형태 bool next_permutation (Iterator first, lIterator last, Compare comp)

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

using namespace std;

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

 

현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true 반환

다음 순열이 없다면 (= 다음에 나온 순열이 순서상 이전 순열보다 작다면) false 반환.

• operator < 사용해서 순열 생성 (default: 오름차순)

 

 

정렬의 필요성

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

using namespace std;

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

    printf("순열\n");
    do {
        for (auto i : v)
        {
            cout << i << " ";
        }
        puts("");
    } while (next_permutation(v.begin(), v.end()));

    printf("\n수행 완료 후\n");
    for (auto i : v)
    {
        cout << i << " ";
    }
    puts("");
}

 

원소 순서가 {3, 1, 2}로 주어졌는데, 순열의 모든 경우의 수가 나오지 않았다.

이는 앞서 말했듯이 내부 동작 비교에서 false 반환 후 끝난 것이다.

 

그렇기에 보통 sort 처리한 후

next_permutation()을 사용하기도 한다.

📌 [C++] sort() 함수란?

📌 [STL] unique 함수 활용한 vector 중복 원소 제거

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

using namespace std;

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

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

    printf("순열\n");
    do {
        for (auto i : v)
        {
            cout << i << " ";
        }
        puts("");
    } while (next_permutation(v.begin(), v.end()));

    printf("\n수행 완료 후\n");
    for (auto i : v)
    {
        cout << i << " ";
    }
    puts("");
}

 

 

내림차순 순열

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
    string s = "cba";

    printf("순열\n");
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end(), greater<int>()));


    printf("\n수행 완료 후\n");
    cout << s << endl;
}

 

문자열도 가능하며, 3번째 인자로 비교 인자를 주어서 내림차순 형태로도 처리할 수 있다.

이때, 주어지는 Data가 내림차순 정렬된 상태여야 한다.

 

또는 내림차순 Data를 prev_permutation로도

내림차순 순열을 구할 수 있다.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string s = "cba";
    printf("순열\n");
    do {
        cout << s << endl;
    } while (prev_permutation(s.begin(), s.end()));

    printf("\n수행 완료 후\n");
    cout << s << endl;
}

 

 

조합

조합도(Combination) 마찬가지로

next_permutation()을 통해 구현할 수 있다.

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

using namespace std;

int main()
{
    vector<int> v{ 1, 2, 3 };
    vector<bool> visited(3, true);
    
    int cnt = 2;
    for (int i = 0; i < v.size() - cnt; i++)
    {
        visited[i] = false;
    }

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

        for (int i = 0; i < v.size(); i++) {
            if (visited[i]) cout << v[i] << " ";
        }
        puts("");

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

 

visited 에서 뽑고 싶은 개수만큼 뒤에 원소를 true로 유지한다.

ex) 3개 중 2개를 뽑는 경우 {false, true, true}

그 후에 next_permutation()에 인자로 visited 를 준다.