C++ next_permutation으로 순열, 조합 구현하기

1. next_permutation 이해하기

• 역할: [first, last) 범위 내 요소를 사전순(next lexicographical order)으로 다음 순열로 바꿈.

• 반환값:

  • 다음 순열이 존재하면 true

  • 다음 순열이 없으면(즉, 마지막 순열이면) false (초기 상태로 돌아가려면 reverse() 사용)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1,3,5,7};
    cout << next_permutation(arr.begin(),arr.end()) << '\n'; // 1 출력 -> True: 다음순서가 있음을 의미
    for(int n : arr) cout << n << " "; // 1 3 7 5  -> 위의 next_permutation으로 다음 순번의 숫자들로 정렬됨

    return 0;
}

2. next_permutation에 쓸 배열은 sort 돼 있어야 한다

ex.

순열구할시

arr = {1,2,3,4}

코드:

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

int main() {
    std::vector<int> v = {1, 2, 3, 4}; // 사전순으로 가장 작은 상태

    do {
        for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
        cout << "\n";
    } while (std::next_permutation(v.begin(), v.end())); // 다음 조합 생성

    return 0;
}

조합 구할 시

arr = {0,0,1,1}

코드:

#include <iostream>
#include <algorithm>
...