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이 작을 때 (대략 10 이하 권장; 11! ≈ 4천만, 12!은 4억 이상)
• 조합을 비트나 next_permutation으로 표현할 때

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

#include <algorithm>
#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>

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 <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 <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
}

std::string도 연속 메모리이므로 begin()/end()로 같은 방식으로 사용할 수 있습니다. 애너그램·암호 후보 생성 등에 활용할 수 있습니다.

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

#include <algorithm>
#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의 정확히 몇 배로 나오는 것을 보고서야 중복을 알아챘습니다. 출력이 많은 문제에서는 눈으로 확인하기 어려우니, 작은 입력으로 개수부터 공식과 맞춰 보는 습관이 이런 버그를 가장 빨리 잡습니다.

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

#include <algorithm>
#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 이하) 사용하는 것이 좋습니다.

// 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()));

활용 패턴 요약

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

// 1. 모든 순열
std::sort(v.begin(), v.end());
do {
    process(v);
} while (std::next_permutation(v.begin(), v.end()));

// 2. k-순열: 앞 k개만 사용하고 뒤쪽을 뒤집어 중복 제거
std::sort(v.begin(), v.end());
do {
    processFirst(v, k);
    std::reverse(v.begin() + k, v.end());
} while (std::next_permutation(v.begin(), v.end()));

// 3. 조합: selector의 순열로 "어떤 k개를 뽑을지" 표현
std::vector<bool> selector(n);
std::fill(selector.begin(), selector.begin() + k, true);
do {
    processCombination(v, selector);
} while (std::prev_permutation(selector.begin(), selector.end()));

실전에서 쓸 때 팁

• 반드시 정렬 먼저: 모든 순열을 돌려야 하면 std::sort(begin, end) 후 루프를 돌리세요. 정렬하지 않으면 “현재 순서부터” 마지막 순열까지만 나옵니다.
• 사전순 의미: “사전순 다음”이므로 문자열처럼 비교됩니다. 정수 벡터면 오름차순이 첫 순열, 내림차순이 마지막 순열입니다.
• n 크기: n이 10 이하일 때만 “전체 순열”을 도는 방식을 쓰는 것이 안전합니다. 11 이상이면 개수가 수천만~수억이 됩니다.
• 중복 원소: 같은 값이 있어도 next_permutation이 사전순으로 다음만 만들기 때문에, 동일한 수열은 한 번만 나와 별도 중복 제거가 필요 없습니다.
• 커스텀 순서: next_permutation(begin, end, comp)처럼 비교자 comp를 넘기면, “사전순”을 그 비교 기준으로 적용할 수 있습니다. 이때 시작점도 같은 비교자로 sort 해야 합니다. 예를 들어 구조체를 score 기준으로 순열을 돌리면서 sort는 기본 operator<(또는 다른 필드)로 했다면, 시작점이 그 비교자 기준의 첫 순열이 아니어서 일부 순열이 빠집니다. 비교자는 strict weak ordering을 만족해야 하며, <=처럼 같은 값에 true를 돌려주는 비교자는 미정의 동작을 부릅니다.

FAQ

Q1: next_permutation과 prev_permutation의 차이는?

A: next_permutation은 사전순 다음 순열로 바꾸고, prev_permutation은 이전 순열로 바꿉니다. 마지막 순열에서 next_permutation을 호출하면 false가 나오고 범위는 첫 순열로 돌아갑니다.

Q2: 정렬을 꼭 해야 하나요?

A: 모든 순열을 한 번씩 돌리려면 반드시 먼저 정렬해야 합니다. 정렬하지 않으면 “현재 배치부터” 마지막 순열까지만 생성됩니다.

Q3: 중복된 원소가 있으면 같은 수열이 여러 번 나오나요?

A: 아니요. 사전순으로 “다음”만 생성하기 때문에 동일한 수열은 한 번만 나옵니다. 예: {1,1,2} → 112, 121, 211 세 가지만 생성됩니다.

Q4: n이 10보다 크면 어떻게 하나요?

A: n!이 급격히 커지므로 “전체 순열”을 도는 방식은 비현실적입니다. 부분만 필요하면 백트래킹이나 조합 생성 등 다른 방법을 고려하세요. STL 알고리즘 가이드에서 sort·partition 등과 함께 쓰는 패턴도 참고할 수 있습니다.

---

같이 보면 좋은 글

• C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
• C++ make_heap·push_heap·pop_heap: priority_queue 대신 힙을 직접 다룰 때
• C++ 범위 기반 for문과 구조화된 바인딩 | 모던 C++ 반복문
• C++ Algorithm Copy
• C++ Algorithm Count
• C++ Algorithm Generate