[C++] next_permutation 함수

 

next_permutation 함수

 

순열이란

n개 중에서 r개를 선택해 나열하는 모든 경우의 수이다. (순서 상관있음)

nPr = n! / (n - r)!

 

예를 들어 5개 중에 5개를 뽑아서 나열하는 모든 경우의 수는 5! = 120이다.

 

 

template <class BidirIt> 
bool next_permutation ( BidirIt first, BidirIt last );

#include <algorithm> 해야 함

 

현재 순열에 대하여 다음 순열을 반환한다.

 

다음 순열을 어디로 반환하는가?

= 원본을 바꿔버린다.

 

현재 순열 값을 확인하고 다음 순열을 반환하기 때문에 

처음부터 끝까지의 순열을 가지고 싶다면 

정렬된 상태에서 시작해야 한다.

 

BidirIt는 아마 Bidirectional Iterator를 의미하는 듯

 

2번째 인자로 비교 함수를 넣을 수도 있다.

 

 

반환값

새로운 순열 값이 이전 순열 값보다

크다면 True를 반환

작다면 False를 반환

즉, 마지막 순열에서 다시 첫 순열로 되돌아가는 경우에만 false를 반환한다고 생각하면 된다.

 

 

 

코드

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

using namespace std;

int main()
{
    // 예시로 사용할 배열
    vector<int> myNumbers = { 1, 2, 3 };

    // 현재 순열 출력
    cout << "현재 순열: ";
    for (int num : myNumbers) {
        cout << num << ' ';
    }
    cout << "\n";

    // 다음 순열 생성
    while (next_permutation(myNumbers.begin(), myNumbers.end())) {
        // 새로운 순열 출력
        cout << "다음 순열: ";
        for (int num : myNumbers) {
            cout << num << ' ';
        }
        cout << "\n";
    }

    return 0;
}