C++ next_permutation으로 순열·조합 만들기: 정렬 후 do-while 패턴

Permutation이란?

순열(permutation) 은 원소들을 다른 순서로 나열한 것입니다. 예를 들어 {1,2,3}의 순열은 123, 132, 213, 231, 312, 321 여섯 가지입니다. C++에서는 std::next_permutation / std::prev_permutation으로 사전순(lexicographic)의 다음·이전 순열을 구할 수 있어, 브루트포스 탐색·스케줄링·후보 생성 등에 사용됩니다.

주로 모든 경우를 확인해야 하는 완전 탐색에서 쓰며, 순열 개수가 n!이므로 n이 작을 때만 현실적입니다(11!은 약 4천만, 12!은 4억이 넘습니다). 뒤에서 보듯 vector<bool> 선택 벡터의 순열을 돌려 조합을 표현하는 데도 쓸 수 있습니다.

아래는 범위를 정렬한 뒤 루프로 모든 순열을 도는 기본 패턴입니다.

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

std::vector<int> v = {1, 2, 3};

// 모든 순열
do {
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));

next_permutation은 현재 순열을 사전순 다음으로 바꾸고 true를 반환합니다. 이미 마지막 순열이면 다음이 없으므로 false를 반환하며, 이때 범위는 사전순 첫 순열(오름차순)로 돌아갑니다. 따라서 위처럼 do-while로 쓰면 첫 순열부터 마지막 순열까지 정확히 한 번씩만 처리할 수 있습니다.

내부 알고리즘을 알면 “왜 정렬이 필요한지”, “왜 중복이 자동으로 걸러지는지”가 한 번에 이해됩니다. next_permutation은 (1) 뒤에서부터 보며 a[i] < a[i+1]인 첫 위치 i를 찾고, (2) 다시 뒤에서부터 a[i]보다 큰 첫 원소 a[j]를 찾아 둘을 바꾼 뒤, (3) i+1부터 끝까지를 뒤집습니다. (1)에서 그런 i가 없다는 것은 전체가 내림차순, 즉 마지막 순열이라는 뜻이므로 전체를 뒤집어 오름차순으로 만들고 false를 반환합니다. 이 함수는 현재 배치만 보고 “바로 다음”을 계산할 뿐 어디서 시작했는지는 모르기 때문에, 시작이 오름차순이 아니면 그보다 앞선 순열은 결코 만들어지지 않습니다. 한 번 호출은 최악 O(n)이지만 전체 순회에서 평균(분할 상환) 비용은 호출당 상수에 가까워서, 전체 비용은 순열을 처리하는 쪽(보통 O(n)씩)이 좌우해 O(n·n!)이 됩니다.

기본 사용

한 번만 “다음/이전”으로 넘기고 싶을 때는 반환값으로 다음 순열이 있었는지 확인할 수 있습니다.

#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 3};

// 다음 순열로 바꾸고, 성공 여부 반환
bool ok = std::next_permutation(v.begin(), v.end());
// v는 {1, 3, 2}, ok == true

// 이전 순열로 되돌리기
std::prev_permutation(v.begin(), v.end());
// v는 다시 {1, 2, 3}

실전 예시

예시 1: 모든 순열 출력

시작점을 오름차순(사전순 첫 순열)으로 맞추기 위해 std::sort를 먼저 호출해야 합니다. 정렬하지 않으면 “현재 순열부터” 마지막 순열까지만 생성되어 앞쪽 순열들이 빠집니다.

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

int main() {
    std::vector<int> v = {1, 2, 3};
    
    // 정렬 (시작점)
    std::sort(v.begin(), v.end());
    
    int count = 0;
    do {
        ++count;
        for (int x : v) {
            std::cout << x;
        }
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));
    
    std::cout << "총 " << count << "개" << std::endl;  // 6
}

n=3이면 3! = 6개이므로 위 루프는 정확히 6번 돌며, 매번 서로 다른 순열이 출력됩니다.

예시 2: 문자열 순열

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

int main() {
    std::string str = "abc";
    
    do {
        std::cout << str << std::endl;
    } while (std::next_permutation(str.begin(), str.end()));
    
    // abc
    // acb
    // bac
    // bca
    // cab
    // cba
}

next_permutation은 양방향 반복자만 요구하므로 std::string도 begin()/end()로 같은 방식으로 사용할 수 있습니다. 애너그램 생성 같은 곳에 활용할 수 있습니다.

예시 3: k-순열 (n개 중 k개 뽑아 순서대로 나열)

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

void kPermutation(std::vector<int> v, int k) {
    std::sort(v.begin(), v.end());

    do {
        for (int i = 0; i < k; ++i) {
            std::cout << v[i] << " ";
        }
        std::cout << std::endl;
        // 뒤쪽 n-k개를 내림차순으로 만들어, 다음 호출이 앞 k개를 바꾸게 함
        std::reverse(v.begin() + k, v.end());
    } while (std::next_permutation(v.begin(), v.end()));
}

int main() {
    std::vector<int> v = {1, 2, 3, 4};
    kPermutation(v, 2);  // 2-순열
}

k-순열은 “앞 k개만 사용”하되, reverse 한 줄이 핵심입니다. 전체 순열을 그대로 돌리면서 앞 k개만 읽으면 같은 k개 접두사가 뒤쪽 n-k개의 배치 수, 즉 (n-k)!번씩 반복해서 나옵니다. {1,2,3,4}에서 2-순열이라면 12가지가 두 번씩, 총 24줄이 출력됩니다. 앞 k개를 처리한 직후 뒤쪽 n-k개를 뒤집으면 뒤쪽이 “그 접두사에서 가능한 마지막 배치(내림차순)“가 되므로, 다음 next_permutation 호출은 뒤쪽 배치를 건너뛰고 접두사 자체를 다음 것으로 바꿉니다. 그 결과 n!/(n-k)!개의 k-순열이 사전순으로 정확히 한 번씩 나옵니다. reverse를 빠뜨리면 출력 개수가 nPk의 (n-k)!배가 되므로, 작은 입력으로 출력 개수를 공식과 맞춰 보면 이런 실수를 빨리 잡을 수 있습니다.

예시 4: 조합 (n개 중 k개 뽑기, 순서 무관)

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

void combination(std::vector<int> v, int k) {
    std::vector<bool> selector(v.size());
    std::fill(selector.begin(), selector.begin() + k, true);
    
    do {
        for (size_t i = 0; i < v.size(); ++i) {
            if (selector[i]) {
                std::cout << v[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (std::prev_permutation(selector.begin(), selector.end()));
}

int main() {
    std::vector<int> v = {1, 2, 3, 4};
    combination(v, 2);  // 2-조합
}

조합은 true/false로 “뽑음/안 뽑음”을 나타내는 selector 벡터를 두며, 이 벡터의 순열을 돌리면 됩니다. prev_permutation을 쓰면 사전순으로 “이전” 조합이 나오므로, fill(..., true)로 앞 k개만 true로 둔 뒤 루프를 돌면 nCk 가지를 모두 생성할 수 있습니다.

여기서 prev_permutation을 쓰는 이유는 시작 상태 때문입니다. true가 false보다 크므로 {T,T,F,F}는 이 값들로 만들 수 있는 사전순 마지막 배치이고, 여기서 prev로 내려가면 {F,F,T,T}까지 모든 배치를 지나갑니다. 선택된 원소가 {1,2}, {1,3}, … 순서로 나와 결과도 보기 좋습니다. 반대로 next_permutation을 쓰고 싶다면 뒤쪽 k개를 true로 채운 {F,F,T,T}에서 시작하면 됩니다. selector 자체가 중복 원소(true k개, false n-k개)의 순열이므로 앞에서 본 “중복은 한 번만” 성질 덕분에 nCk개가 정확히 나오는 것입니다. n이 작다면 비트마스크(for (int m = 0; m < (1 << n); ++m) if (popcount(m) == k))도 같은 결과를 주지만, 2^n개를 모두 훑으므로 k가 작을 때는 selector 방식이 더 효율적입니다.

자주 발생하는 문제

문제 1: 정렬

std::vector<int> v = {3, 1, 2};

// 정렬 안 됨
do {
    // 일부 순열만 생성
} while (std::next_permutation(v.begin(), v.end()));

// 정렬 후
std::sort(v.begin(), v.end());
do {
    // 모든 순열 생성
} while (std::next_permutation(v.begin(), v.end()));

문제 2: 반환값으로 “다음이 있었는지” 확인

next_permutation은 다음 순열로 바꾼 뒤 “다음이 있었는지”를 bool로 반환합니다. 마지막 순열에서 한 번 더 호출하면 false가 나오고, 이때 범위는 사전순 첫 순열(오름차순)로 초기화됩니다. while로 쓸 때는 “첫 순열”을 먼저 처리할지, do-while으로 첫 순열부터 돌지 정하면 됩니다.

std::vector<int> v = {1, 2, 3};

// next_permutation은 bool 반환
while (std::next_permutation(v.begin(), v.end())) {
    // 순열 처리 (첫 순열 123은 여기서 처리 안 됨!)
}

// 마지막 순열(321) 다음은 없으므로 false, v는 123으로 돌아감

문제 3: 중복

std::vector<int> v = {1, 1, 2};

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

do {
    for (int x : v) {
        std::cout << x;
    }
    std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));

// 112
// 121
// 211
// 중복 자동 처리

같은 값이 여러 개 있으면 같은 수열은 한 번만 나옵니다. next_permutation이 사전순으로 “다음”만 만들기 때문에, 중복 조합을 따로 걸러 줄 필요가 없습니다.

문제 4: n이 크면 순열 개수가 폭발함

순열 개수는 n!이라서 n이 조금만 커져도 매우 커집니다. n=10이면 약 362만, n=12면 약 4억 7천만이므로, “모든 순열”을 도는 방식은 n이 작을 때만(보통 10 이하) 사용하는 것이 좋습니다.

#include <numeric>  // std::iota

// n! 순열
// n=10: 3,628,800
// n=12: 479,001,600

// 큰 n은 비현실적
std::vector<int> v(15);
std::iota(v.begin(), v.end(), 1);

// 너무 많음
// do { /* ... */ } while (std::next_permutation(v.begin(), v.end()));

직접 실행해 본 결과

Apple clang 21.0.0(libc++), -std=c++20 -O2, macOS arm64에서 위 설명을 하나씩 확인했습니다.

확인 항목	결과
정렬 안 한 {3,1,2}에서 do-while	순열 2개만 나옴(312, 321). 3! = 6개가 아님
{1,2,3}에서 while (next_permutation)이 false가 된 뒤의 값	123으로 되돌아와 있음
{1,1,2,2} 전체 순열	6개 (4! = 24가 아니라 4!/(2!·2!) = 6)
k-순열: {1,2,3,4}, k=2, 루프마다 reverse(begin+k, end)	12개 = P(4,2)
조합: vector<bool> 5칸 중 앞 2칸 true, prev_permutation	10개 = C(5,2)

n이 커질 때 순열 전체를 도는 시간도 쟀습니다. 본문에서는 첫 원소를 더하는 일만 해서, 실제 작업을 넣으면 이보다 훨씬 오래 걸립니다. 값은 두 번 실행해 비슷하게 나온 범위입니다.

n	순열 개수	걸린 시간
8	40,320	약 0.1ms
9	362,880	약 0.8ms
10	3,628,800	약 8~11ms
11	39,916,800	약 85~94ms

n이 1 늘 때마다 개수가 n배가 되는 것이 시간에도 그대로 보입니다. 다만 이것은 본문이 거의 비어 있는 반복의 하한입니다. 순열마다 1µs짜리 검사를 넣으면 n=11에서만 40초가 걸리므로, n=10 안팎을 넘기면 가지치기를 고려하세요.

활용 패턴 요약

목적	패턴
모든 순열	sort 후 do { process(v); } while (next_permutation(...));
k-순열	같은 루프에서 앞 k개만 사용하고, 처리 후 reverse(v.begin()+k, v.end())
조합 (nCk)	vector<bool>로 뽑을 위치 표시 후, 이 벡터에 prev_permutation 적용

커스텀 비교자를 쓸 때

next_permutation(begin, end, comp)처럼 비교자를 넘기면 “사전순”이 그 비교 기준으로 바뀝니다. 이때 시작점도 같은 비교자로 sort해야 합니다. 예를 들어 구조체를 score 기준으로 순열을 돌리면서 sort는 다른 필드 기준으로 했다면, 시작점이 그 비교자 기준의 첫 순열이 아니어서 일부 순열이 빠집니다. 비교자는 strict weak ordering을 만족해야 하며, <=처럼 같은 값에 true를 돌려주는 비교자를 넘기면 미정의 동작이 됩니다.

부분 순열만 필요하거나 n이 10을 넘는다면 가지치기가 가능한 백트래킹을 검토하는 편이 낫습니다. STL 알고리즘 기초에서 sort·partition 등과 함께 쓰는 패턴도 참고할 수 있습니다.

참고 자료

• cppreference: std::next_permutation

---

같이 보면 좋은 글

• C++ make_heap·push_heap·pop_heap: priority_queue 대신 힙을 직접 다룰 때
• C++ std::copy·copy_if·copy_backward: 목적지 크기, 겹치는 범위, back_inserter
• C++ count·count_if와 all_of·any_of·none_of로 조건 집계하기
• C++ fill·generate·iota로 범위 채우기