C++ Algorithm Permutation | "Permutation Algorithm" Guide

· 12분 읽기 · 수정 Intermediate Tutorial
C++ Algorithm Permutation | "Permutation Algorithm" Guide

이 글의 핵심

next_permutation, prev_permutation: lexicographic order, sort first, duplicate handling—STL combinatorics for interviews.

What is a permutation?

A permutation is an arrangement of elements in a different order. For example, the permutations of {1,2,3} are 123, 132, 213, 231, 312, and 321, making a total of six permutations. In C++, you can use std::next_permutation and std::prev_permutation to compute the next/previous permutation in lexicographic order, which is useful for brute-force searches, scheduling, generating password candidates, and more.

Duplicates: If the range contains equal elements, some permutations look identical unless you treat indices as distinct—sorting first makes next_permutation visit distinct rearrangements of multiset values in lexicographic order.

When should you use it?

  • When you need to check all possible cases (brute-force search)
  • When n is small (recommended for n around 10 or less; note that 11! ≈ 40 million, and 12! exceeds 400 million)
  • When representing combinations using bit manipulation or next_permutation

Below is the basic pattern for iterating through all permutations. Make sure to sort the range first.

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

How it works: next_permutation modifies the current permutation to the next lexicographic order and returns true. If it is already the last permutation, it returns false and resets the range to the first lexicographic order (ascending order). Using a do-while loop ensures that each permutation is processed exactly once, starting from the first to the last.

Basic Usage

If you only want to move to the “next/previous” permutation once, you can check the return value to determine whether a next permutation exists.

#include <algorithm>

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

// Move to the next permutation and check if successful
bool ok = std::next_permutation(v.begin(), v.end());
// v is now {1, 3, 2}, ok == true

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

Practical Examples

Example 1: Print All Permutations

To ensure the starting point is the ascending order (first lexicographic permutation), it is important to call std::sort first. If you skip sorting, only the permutations from the “current order” to the last permutation will be generated, and earlier permutations will be skipped.

#include <algorithm>
#include <vector>

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

If n = 3, there are 3! = 6 permutations, so the loop will run exactly 6 times, printing a unique permutation each time.

Example 2: String Permutations

#include <algorithm>
#include <string>

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

Since std::string is stored in contiguous memory, you can use begin()/end() in the same way. This is useful for generating anagrams or password candidates.

Example 3: k-Permutations (Choose k elements from n and arrange them)

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

For k-permutations, you only need to use the first k elements in each iteration. Since next_permutation rearranges the entire range, you can process only the first k elements to generate all possible ordered selections of k elements from n.

Example 4: Combinations (Choose k elements from n, order does not matter)

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

For combinations, use a vector<bool> to indicate which elements to select (true for selected, false for not selected). By applying prev_permutation to this selector vector, you can generate all combinations of size k in lexicographic order.

Common Issues

Issue 1: Not Sorting

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

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

// ✅ Sorted first
std::sort(v.begin(), v.end());
do {
    // All permutations are generated
} while (std::next_permutation(v.begin(), v.end()));

Issue 2: Checking the Return Value

next_permutation returns a bool indicating whether the next permutation exists. When called on the last permutation, it returns false and resets the range to the first lexicographic permutation (ascending order). Decide whether to process the “first permutation” before entering the loop or use a do-while loop to handle it.

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

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

// After the last permutation (321), false is returned, and v resets to 123

Issue 3: Handling 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()));

// Output:
// 112
// 121
// 211
// Duplicates are automatically handled

If there are duplicate elements, identical permutations will only appear once. Since next_permutation generates only the next lexicographic order, no additional filtering is needed.

Issue 4: Large n Causes Combinatorial Explosion

The number of permutations grows as n!, which becomes extremely large as n increases. For example, when n = 10, there are about 3.6 million permutations, and for n = 12, there are over 479 million. Iterating through all permutations is only feasible for small values of n (typically 10 or less in practical scenarios).

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

// Too many permutations for large n
std::vector<int> v(15);
std::iota(v.begin(), v.end(), 1);

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

Summary of Usage Patterns

PurposePattern
All permutationssort first, then do { process(v); } while (next_permutation(...));
k-permutationsUse the first k elements in each iteration
Combinations (nCk)Use a vector<bool> to indicate selected positions, then apply prev_permutation
// 1. All permutations
std::sort(v.begin(), v.end());
do {
    process(v);
} while (std::next_permutation(v.begin(), v.end()));

// 2. k-permutations: Use only the first k elements
do {
    processFirst(v, k);
} while (std::next_permutation(v.begin(), v.end()));

// 3. Combinations: Use a selector vector to represent which k elements to pick
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

  • Always sort first: If you need to iterate through all permutations, call std::sort(begin, end) before starting the loop. Without sorting, only permutations from the “current order” to the last permutation will be generated.
  • Lexicographic order: “Next lexicographic order” means it behaves like dictionary order. For integer vectors, ascending order is the first permutation, and descending order is the last permutation.
  • Small n: Iterating through all permutations is only practical for small n (usually 10 or less). For n greater than 10, the number of permutations becomes prohibitively large.
  • Duplicate elements: If there are duplicate elements, next_permutation automatically handles them, so you don’t need to filter out duplicates separately.
  • Custom order: You can pass a custom comparator to next_permutation(begin, end, comp) to define your own lexicographic order.

FAQ

Q1: What is the difference between next_permutation and prev_permutation?

A: next_permutation modifies the range to the next lexicographic permutation, while prev_permutation modifies it to the previous lexicographic permutation. If next_permutation is called on the last permutation, it returns false and resets the range to the first permutation.

Q2: Is sorting necessary?

A: Yes, sorting is necessary if you want to iterate through all permutations. Without sorting, only permutations from the “current order” to the last permutation will be generated.

Q3: Will duplicate elements result in duplicate permutations?

A: No, next_permutation ensures that identical permutations are generated only once, even if there are duplicate elements in the input.

Q4: What if n is greater than 10?

A: Since the number of permutations grows exponentially with n, iterating through all permutations becomes impractical for large n. For n > 10, consider alternative methods like backtracking or generating only a subset of permutations. Check out the STL Algorithm Guide for more patterns using sort and partition.

Here are some related posts for further reading:

Practical Tips

Here are some tips for applying these concepts in real-world scenarios:

Debugging Tips

  • Check compiler warnings first if issues arise.
  • Use simple test cases to reproduce the problem.

Performance Tips

  • Avoid premature optimization without profiling.
  • Set measurable performance goals before optimizing.

Code Review Tips

  • Anticipate common feedback during code reviews.
  • Follow your team’s coding conventions.

Checklist for Practical Application

Use this checklist to ensure you apply these concepts effectively in real-world scenarios.

Before Writing Code

  • Is this technique the best solution for the current problem?
  • Can your team understand and maintain this code?
  • Does it meet performance requirements?

While Writing Code

  • Have you resolved all compiler warnings?
  • Have you considered edge cases?
  • Is error handling appropriate?

During Code Review

  • Is the intent of the code clear?
  • Are there sufficient test cases?
  • Is the code properly documented?

Use this checklist to minimize mistakes and improve code quality.

Keywords Covered in This Post (Related Search Terms)

Search for terms like C++, algorithm, permutation, combination, and STL to find more resources related to this post.