C++ Algorithm Permutation | "Permutation Algorithm" Guide

2026년 3월 12일 · 12분 읽기 · 수정 2026년 3월 12일 Intermediate Tutorial

이 글의 핵심

Practical guide for C++ Algorithm Permutation.

What is Permutation?

Permutation is arranging elements in different order. For example, permutations of {1,2,3} are 123, 132, 213, 231, 312, 321 — six cases. In C++, std::next_permutation / std::prev_permutation can get next/previous permutation in lexicographic order, used for brute force search, scheduling, password candidate generation, etc.

When to Use?

When need to check all cases (brute force)
When n is small (roughly 10 or less recommended; 11! ≈ 40 million, 12! is over 400 million)
When expressing combinations with bits or next_permutation

Below is basic pattern that must sort range first then loop through all permutations.

#include <algorithm>
#include <vector>

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

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

Behavior: next_permutation changes current permutation to lexicographic next and returns true. If already last permutation, no next exists so returns false, and range returns to lexicographic first permutation (ascending). So using do-while like above processes exactly once from first to last permutation.

Basic Usage

When wanting to move to “next/previous” just once, can check whether next permutation existed with return value.

#include <algorithm>

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

// Change to next permutation and return success
bool ok = std::next_permutation(v.begin(), v.end());
// v is {1, 3, 2}, ok == true

// Revert to previous permutation
std::prev_permutation(v.begin(), v.end());
// v is back to {1, 2, 3}

Practical Examples

Example 1: Print All Permutations

Important to call std::sort first to match starting point to ascending (lexicographic first permutation). Without sorting, generates only “from current permutation” to last, missing earlier permutations.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    
    // Sort (starting point)
    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 << "Total " << count << " permutations" << std::endl;  // 6
}

For n=3, 3! = 6, so above loop runs exactly 6 times, printing different permutation each time.

Example 2: String Permutation

#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 is also contiguous memory, so can use same way with begin()/end(). Can use for anagrams, password candidate generation, etc.

Example 3: k-Permutation (Choose k from n, arrange in order)

#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;
    } while (std::next_permutation(v.begin(), v.end()));
}

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

k-permutation just “uses only first k”. Since next_permutation rearranges entire, reading only first k each time gets all cases of choosing k from n and arranging in order.

Example 4: Combination (Choose k from n, order irrelevant)

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

Combination uses selector vector representing “chosen/not chosen” with true/false, and rotates permutations of this vector. Using prev_permutation gives “previous” combination in lexicographic order, so filling only first k with true then looping generates all nCk cases.

Common Problems

Problem 1: Sorting

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

// ❌ Not sorted
do {
    // Generates only some permutations
} while (std::next_permutation(v.begin(), v.end()));

// ✅ After sorting
std::sort(v.begin(), v.end());
do {
    // Generates all permutations
} while (std::next_permutation(v.begin(), v.end()));

Problem 2: Check “Whether Next Existed” with Return Value

next_permutation changes to next permutation then returns bool for “whether next existed”. Calling once more on last permutation returns false, and range is initialized to lexicographic first permutation (ascending). When using while, decide whether to process “first permutation” first, or use do-while to loop from first.

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

// next_permutation returns bool
while (std::next_permutation(v.begin(), v.end())) {
    // Process permutation (first permutation 123 not processed here!)
}

// After last permutation (321), no next so false, v returns to 123

Problem 3: Duplicates

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
// Duplicates handled automatically

When same values exist multiple times, same sequence appears only once. Since next_permutation generates only lexicographic “next”, no need to filter duplicate combinations separately.

Problem 4: Permutation Count Explodes When n is Large

Permutation count is n!, so gets very large with slight increase in n. For n=10 about 3.6 million, n=12 about 470 million, so “all permutations” method should only be used when n is small (usually 10 or less in practice).

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

// Large n is unrealistic
std::vector<int> v(15);
std::iota(v.begin(), v.end(), 1);

// ❌ Too many
// do { /* ... */ } while (std::next_permutation(v.begin(), v.end()));

Usage Pattern Summary

Purpose	Pattern
All permutations	After `sort`, `do { process(v); } while (next_permutation(...));`
k-permutation	Use only first k of `v` each time in same loop
Combination (nCk)	Mark positions to choose with `vector<bool>`, apply `prev_permutation` to this vector

// 1. All permutations
std::sort(v.begin(), v.end());
do {
    process(v);
} while (std::next_permutation(v.begin(), v.end()));

// 2. k-permutation: Use only first k each time
do {
    processFirst(v, k);
} while (std::next_permutation(v.begin(), v.end()));

// 3. Combination: Express "which k to choose" with selector permutations
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()));

Practical Tips

Must sort first: If need to loop all permutations, call std::sort(begin, end) then loop. Without sorting, generates only “from current order” to last permutation.
Lexicographic meaning: “Lexicographic next” so compared like strings. For integer vector, ascending is first permutation, descending is last.
n size: Safe to use “all permutations” method only when n is 10 or less. For 11 or more, count becomes tens of millions to hundreds of millions.
Duplicate elements: Even with same values, next_permutation generates only lexicographic next, so identical sequence appears only once, no separate duplicate removal needed.
Custom order: Passing comparator comp like next_permutation(begin, end, comp) applies “lexicographic” with that comparison criteria.

FAQ

Q1: What is difference between next_permutation and prev_permutation?

A: next_permutation changes to lexicographic next permutation, prev_permutation changes to previous. Calling next_permutation on last permutation returns false and range returns to first permutation.

Q2: Must I sort?

A: To loop all permutations once each, must sort first. Without sorting, generates only “from current arrangement” to last permutation.

Q3: Do duplicate elements cause same sequence multiple times?

A: No. Since generates only lexicographic “next”, identical sequence appears only once. Example: {1,1,2} → generates only 112, 121, 211 three cases.

Q4: What if n is larger than 10?

A: n! grows rapidly, so “all permutations” method is unrealistic. If only partial needed, consider other methods like backtracking or combination generation. STL Algorithm Guide also references patterns using with sort, partition, etc.

C++ Algorithm | “STL algorithm” Core Summary
C++ Algorithm Heap | “Heap Algorithm” Guide
C++ Range-based for | “Range-based for” Guide
C++ Algorithm Copy
C++ Algorithm Count
C++ Algorithm Generate

Practical Tips

Tips you can apply immediately in practice.

Debugging Tips

Check compiler warnings first when problems occur
Reproduce problem with simple test cases

Performance Tips

Don’t optimize without profiling
Set measurable metrics first

Code Review Tips

Pre-check frequently pointed out parts in code reviews
Follow team coding conventions

Practical Checklist

Items to check when applying this concept in practice.

Before Writing Code

Is this technique the best way to solve current problem?
Can team members understand and maintain this code?
Does it meet performance requirements?

While Writing Code

Resolved all compiler warnings?
Considered edge cases?
Is error handling appropriate?

During Code Review

Is code intent clear?
Are test cases sufficient?
Is it documented?

Use this checklist to reduce mistakes and improve code quality.

Keywords

C++, Algorithm, Permutation, Combination, STL, next_permutation, prev_permutation, Lexicographic, Brute Force

Quick Reference

// All permutations
std::sort(v.begin(), v.end());
do {
    // Process permutation
} while (std::next_permutation(v.begin(), v.end()));

// k-permutation (choose k from n, arrange)
do {
    for (int i = 0; i < k; ++i) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));

// Combination (choose k from n, order irrelevant)
std::vector<bool> selector(n);
std::fill(selector.begin(), selector.begin() + k, true);
do {
    for (size_t i = 0; i < n; ++i) {
        if (selector[i]) {
            std::cout << v[i] << " ";
        }
    }
    std::cout << std::endl;
} while (std::prev_permutation(selector.begin(), selector.end()));

이 글의 핵심

What is Permutation?

Basic Usage

Practical Examples

Example 1: Print All Permutations

Example 2: String Permutation

Example 3: k-Permutation (Choose k from n, arrange in order)

Example 4: Combination (Choose k from n, order irrelevant)

Common Problems

Problem 1: Sorting

Problem 2: Check “Whether Next Existed” with Return Value

Problem 3: Duplicates

Problem 4: Permutation Count Explodes When n is Large

Usage Pattern Summary

Practical Tips

FAQ

Q1: What is difference between next_permutation and prev_permutation?

Q2: Must I sort?

Q3: Do duplicate elements cause same sequence multiple times?

Q4: What if n is larger than 10?

Related Posts

Practical Tips

Debugging Tips

Performance Tips

Code Review Tips

Practical Checklist

Before Writing Code

While Writing Code

During Code Review

Keywords

Quick Reference