순열 구하는 STL 함수 next_permutation(), prev_permutation()

 

 

📌 순열 구하는 STL 함수 next_permutation(), prev_permutation()

순열을 쉽게 구할 수 있는 next_permutation()과 prev_permutation() 함수가 있다.
이 두 함수는 주어진 데이터(벡터나 배열 등)를 정렬된 상태로부터 다음 순열 또는 이전 순열을 구하는 데 유용하다.

 

✅ next_permutation() 함수

bool next_permutation(Iterator first, Iterator last);

🔎동작 원리:

• 현재 컨테이너가 사전순으로 가장 마지막 순열이면 false를 반환하고 처음 순열로 바꾼다.
• 그렇지 않으면 다음 순열을 구하고 true를 반환한다.

 

✅ prev_permutation() 함수

bool prev_permutation(Iterator first, Iterator last);

🔎동작 원리:

• 현재 컨테이너가 사전순으로 가장 작은 순열이면 false를 반환하고 마지막 순열로 바꾼다.
• 그렇지 않으면 이전 순열을 구하고 true를 반환한다.

 

---

 

📍 vector의 모든 순열 구하기

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

using namespace std;

int main()
{
    vector<int> v = { 1,2,3 };
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
    /*
     결과
     1 2 3
     1 3 2
     2 1 3
     2 3 1
     3 1 2
     3 2 1
    */


    vector<int> v = { 3,2,1 };
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (prev_permutation(v.begin(), v.end()));
    /*
     결과
     3 2 1
     3 1 2
     2 3 1
     2 1 3
     1 3 2
     1 2 3
    */

    return 0;
}

 

 

📍 길이가 3인 순열을 모두 출력, 단 순열의 첫번째 요소는 1일 경우만

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

using namespace std;

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

    do {
        if (v[0] == 1)
        {
            for (int i = 0; i < 3; ++i)
            {
                cout << v[i] << " ";
            }
            cout << endl;
        }
    } while (next_permutation(v.begin(), v.end()));
    /*
      결과
      1 2 3
      1 2 4
      1 3 2
      1 3 4
      1 4 2
      1 4 3
    */

    return 0;
}

 

---

 

🔔 정리

🔎 언제 사용하면 좋을까?

 

• 특정 문제에서 모든 가능한 순열을 탐색하는 경우 (예: 완전 탐색 문제).
• 데이터를 사전순으로 정렬해서 순차적으로 처리할 때.

🟢 장점

• 간결하고 직관적: 복잡한 순열 알고리즘을 직접 구현할 필요 없이 간단히 순열을 생성할 수 있다.
• 효율적: 사전순으로 순열을 구하기 위해 내부적으로 효율적인 알고리즘이 구현되어 있다.

🔴 단점

• 정렬된 상태 요구: 처음 순열을 구하기 위해 입력 데이터를 사전순으로 정렬된 상태로 두는 것이 권장된다.
• 메모리 사용: 많은 순열을 다루거나 큰 컨테이너에 대해 순열을 구하면 메모리 사용량이 증가할 수 있다.