next_permutation의 원리, 활용 (순열, 조합)

1. next_permutation 함수란?

현재 순열(permutation)에서 다음 사전순 순열을 생성하는 함수이다. 

이때, 순열 자체를 반환하는 것이 아니라, 원본 데이터를 직접 변경한다.
next_permutation을 호출할 때마다 컨테이너(vector, string, array 등)의 요소가 다음 사전순 순열로 변경된다.
모든 순열을 생성할 수 있다.

next_permutation의 반환값은 bool 값이다.
다음으로 생성할 순열이 존재하면 true를 반환하며, 다음으로 생성할 순열이 없다면 false를 반환한다.
do-while문을 이용해 깔끔하게 사용할 수 있다.

 

C++의 next_permutation은 algorithm 헤더에 포함되어 있다. 

 

2. 기본 사용 예제 (순열)

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

int main() {
    vector<int> v = {1, 2, 3};  // 오름차순 정렬된 초기 순열

    do {
        for (int num : v) cout << num << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));  // 다음 순열 생성

    return 0;
}

 

결과

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

3. 기본 사용 예제 (조합)

기본 아이디어 : 이진 배열(마스크) 기법 사용

예를 들어, n = 5 개의 원소 중 r = 3개를 뽑는 경우, 배열을 [1, 1, 1, 0, 0] 형태로 초기화한다.

이때, 1이 선택할 원소를 의미한다.

 

마스크 기법을 활용하는 이유

조합은 순열과 달리 원소의 순서는 고려하지 않고, 특정 개수의 원소를 선택하는 문제이다.

즉, nCr을 구하는 문제에서 r개의 원소를 선택하는 모든 조합을 만들기 위해 사용된다.

 

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

void printCombinations(vector<int>& numbers, int r) {
    int n = numbers.size();
    vector<int> mask(n, 0);

    // 선택할 개수(r)만큼 1을 할당 (ex: {1, 1, 0, 0})
    for (int i = 0; i < r; i++) mask[i] = 1;

    sort(mask.begin(), mask.end());  // ✅ 정렬된 상태에서 시작

    do {
        for (int i = 0; i < n; i++) {
            if (mask[i]) cout << numbers[i] << " ";  // ✅ 1이 있는 위치의 숫자 출력
        }
        cout << endl;
    } while (next_permutation(mask.begin(), mask.end()));  // ✅ 모든 조합 생성

}

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};  // 원소 5개
    int r = 3;  // 3개 선택

    printCombinations(numbers, r);

    return 0;
}

 

mask의 변화 과정

순서	mask 상태	선택된 원소
1	[1, 1, 1, 0, 0]	{1, 2, 3}
2	[1, 1, 0, 1, 0]	{1, 2, 4}
3	[1, 1, 0, 0, 1]	{1, 2, 5}
4	[1, 0, 1, 1, 0]	{1, 3, 4}
5	[1, 0, 1, 0, 1]	{1 ,3 ,5}
6	[1, 0, 0, 1, 1]	{1, 4, 5}
7	[0, 1, 1, 1, 0]	{2, 3, 4}
8	[0, 1, 1, 0, 1]	{2, 3, 5}
9	[0, 1, 0, 1, 1]	{2, 4, 5}
10	[0, 0, 1, 1, 1]	{3, 4, 5}

 

주의해야 할 점

올바르게 next_permutation() 사용하려면 mask를 처음부터 사전순으로 정렬된 상태(1이 앞쪽, 0이 뒤쪽)로 설정해야 한다.

 

예)

mask 배열을 [1, 1, 0]으로 시작하였다면... -> {1, 2} (사전순으로 시작 O)

mask 배열을 [0, 1, 1]으로 시작하였다면... -> {2, 3} (사전순으로 시작 X)