C++ next_permutation and prev_permutation: All Permutations, Duplicates and Combinations

The one pattern you need

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

int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end());           // start at the first permutation
    do {
        for (int x : v) std::cout << x;
        std::cout << '\n';
    } while (std::next_permutation(v.begin(), v.end()));
}

This prints 123 132 213 231 312 321. The two parts that matter:

• std::sort first. next_permutation doesn’t enumerate “all” permutations. It moves the range to the next one in lexicographic order. Without the sort, {3, 1, 2} visits only 312 and 321, then stops.
• do/while, not while. while (next_permutation(...)) advances before the first iteration, so it skips the starting arrangement.

After the loop ends, next_permutation has returned false and wrapped the range back to ascending order. You don’t need to re-sort if you enumerate again.

The state of the enumeration lives entirely in the range itself — there is no hidden iterator or counter. That makes the API tiny, but it also means you must not modify the elements inside the loop body. If the body swaps two elements or overwrites one while “trying something”, the next call continues from the modified arrangement, and the sequence skips or repeats permutations with no error. Work on a copy inside the body when you need to mutate.

prev_permutation is the mirror image. Start from descending order and it walks backwards to ascending. Both live in <algorithm>, require bidirectional iterators (so they work on std::vector, std::string, std::deque, std::list and raw arrays), and are constexpr since C++20.

---

How the algorithm works

Understanding the algorithm explains the sort requirement and the complexity. To get the next permutation:

1. Scan from the right for the first position i where a[i] < a[i+1]. Everything to the right of i is non-increasing, so it’s already the largest arrangement of that suffix.
2. If no such i exists, the whole range is descending. That’s the last permutation: reverse the range and return false.
3. Otherwise, find the rightmost j with a[j] > a[i], swap them, and reverse the suffix after i so it becomes the smallest arrangement.

template <class It>
bool my_next_permutation(It first, It last) {
    if (first == last) return false;
    It i = last; --i;
    if (i == first) return false;
    while (true) {
        It i1 = i; --i;
        if (*i < *i1) {
            It j = last;
            while (!(*i < *--j)) {}
            std::iter_swap(i, j);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) { std::reverse(first, last); return false; }
    }
}

I checked this against std::next_permutation on a range with duplicates ({1,1,2,3}), and it produced the same sequence. A few consequences follow:

• Complexity. One call is O(n) in the worst case (the standard caps it at n/2 swaps). Over a full enumeration, most calls only touch the last couple of elements, so the amortized cost per permutation is constant. The real cost is n!.
• Only operator< is used. That’s why duplicates are handled for free (next section). It’s also why a custom type needs operator< or a comparator. Without one, you get a template error from inside the standard library headers (GCC reports it in bits/predefined_ops.h) that reads no match for 'operator<' (operand types are 'T' and 'T'), with your type’s name in place of T.

---

Duplicates are handled automatically

std::string s = "aab";
do std::cout << s << ' ';
while (std::next_permutation(s.begin(), s.end()));
// aab aba baa

Three results, not 3! = 6. Equal elements compare equivalent, so the algorithm never produces the same arrangement twice. You don’t need std::set or std::unique to deduplicate. The count is the multinomial coefficient n! / (c1! · c2! · …).

This only holds if the range starts sorted. If you start from an arbitrary order, you still get distinct arrangements, but only the ones lexicographically at or after the starting point.

“Equal” here means equivalent under the comparator, not ==. With a case-insensitive comparator, "A" and "a" are equivalent, so {"A", "a", "b"} produces 3 arrangements instead of 6 — the algorithm treats the two strings as interchangeable and never swaps them relative to each other. That is correct behavior, but it surprises people who expected every distinct value to appear. The same applies to structs compared by one field: two records with the same key count as duplicates even if their other fields differ, so arrangements that differ only in the order of those two records are skipped.

---

Custom order

Pass a comparator, and use the same comparator for the initial sort:

std::vector<int> d = {1, 2, 3};
std::sort(d.begin(), d.end(), std::greater<>());
do { /* 321 312 231 213 132 123 */ }
while (std::next_permutation(d.begin(), d.end(), std::greater<>()));

The bug I’ve watched people chase for a while is sorting with one ordering and permuting with another. For example, they sort structs by id and then call next_permutation with a comparator on name. The loop runs and produces valid-looking output, but it starts in the middle of the sequence, so some arrangements silently never appear. If a brute-force answer is “sometimes wrong”, check this before anything else.

---

k-permutations: the common snippet is wrong

Many tutorials generate ordered selections of k out of n like this:

do {
    use(v[0], ..., v[k-1]);
} while (std::next_permutation(v.begin(), v.end()));

This visits every full permutation and looks at the first k elements. For n = 4, k = 2, that’s 24 iterations, and each 2-prefix appears (n−k)! = 2 times. If you’re counting or summing results, the answer is inflated.

The fix is one line. After you use the prefix, reverse the suffix. The suffix becomes descending, which is its last arrangement, so the next call advances the prefix:

std::vector<int> w = {1, 2, 3, 4};   // sorted
int k = 2;
do {
    for (int i = 0; i < k; ++i) std::cout << w[i];
    std::cout << ' ';
    std::reverse(w.begin() + k, w.end());
} while (std::next_permutation(w.begin(), w.end()));
// 12 13 14 21 23 24 31 32 34 41 42 43   (12 = 4!/2!)

---

Combinations (n choose k)

For unordered selections, permute a selector rather than the data:

std::vector<int> items = {1, 2, 3, 4};
std::vector<bool> sel(items.size(), false);
std::fill(sel.begin(), sel.begin() + 2, true);   // k = 2: T T F F

do {
    for (size_t i = 0; i < items.size(); ++i)
        if (sel[i]) std::cout << items[i];
    std::cout << ' ';
} while (std::prev_permutation(sel.begin(), sel.end()));
// 12 13 14 23 24 34

T T F F is the lexicographically largest arrangement of the selector (since true > false), so you walk down with prev_permutation. That emits combinations in lexicographic order of the chosen indices. The equivalent with next_permutation is a std::vector<int> with n-k zeros followed by k ones. It works just as well, but the output order is reversed.

std::vector<bool> is a packed specialization whose elements are proxy objects, not real bools. prev_permutation still works on it because it only needs iter_swap and comparisons, which the proxies support, but it is slower than permuting a std::vector<char> or std::vector<int>. If you profile a combination-heavy loop, switching the selector type is a cheap win. Also, the data vector itself is never reordered here — only the selector moves — so items does not need to be sorted, only the selector does.

For small n (up to 20 or so), iterating a bitmask from 0 to (1 << n) - 1 and filtering by __builtin_popcount(mask) == k (or std::popcount in C++20) is often simpler. See bit manipulation.

---

C++20 ranges versions

std::vector<int> r = {1, 2, 3};
auto res = std::ranges::next_permutation(r);   // r == {1, 3, 2}
if (res.found) { /* ... */ }

std::ranges::next_permutation takes a range and an optional comparator and projection. It returns next_permutation_result with .in (the end iterator) and .found (the bool), instead of a plain bool. The projection is handy for permuting structs by one field: std::ranges::next_permutation(people, {}, &Person::id). Sort with the same projection first. The ranges version works with GCC 10.

---

When n! is too big

n	n!
8	40,320
10	3,628,800
11	39,916,800
12	479,001,600

Brute-force enumeration is fine up to about n = 10 when the per-permutation work is O(n). Past that, the choice depends on the problem:

• Need only some permutations, or can reject partial ones early. Use backtracking with pruning. It abandons a prefix as soon as it can’t lead to a valid answer, which next_permutation can’t do.
• Need the optimal ordering (TSP-like problems). Use DP over subsets (dp[mask][last]), which is O(2ⁿ · n²) instead of O(n!).
• Need the k-th permutation. Compute it directly with the factorial number system instead of stepping k times:

std::vector<int> kth_permutation(int n, long long k) {   // k is 0-based
    std::vector<long long> fact(n + 1, 1);
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    std::vector<int> pool(n);
    std::iota(pool.begin(), pool.end(), 1);              // <numeric>
    std::vector<int> out;
    for (int i = n; i >= 1; --i) {
        long long idx = k / fact[i - 1];
        k %= fact[i - 1];
        out.push_back(pool[idx]);
        pool.erase(pool.begin() + idx);
    }
    return out;
}
// kth_permutation(4, 9) == {2, 3, 4, 1}, the same result as calling next_permutation 9 times from {1,2,3,4}

long long holds factorials up to 20!, so this works for n ≤ 20. For more, use a big-integer type.

The idea is that the first element changes only every (n−1)! permutations, so k / (n−1)! tells you which remaining value leads, and the remainder is the index within that block. The pool.erase makes the function O(n²), which is irrelevant for n ≤ 20. The inverse operation — “what is the rank of this permutation?” — uses the same factorial weights, counting for each position how many smaller unused values remain. Both come up in puzzle-state encodings, where a permutation is packed into an integer so it can index an array instead of a hash map.

---

Brute force as a test oracle

The most practical use of next_permutation I have found outside of programming contests is testing. When you write a clever greedy or DP solution for an ordering problem — scheduling jobs, arranging items to minimize a cost — enumerate every permutation for small inputs (n ≤ 8), compute the true optimum, and compare it with the clever answer on thousands of random cases. Greedy algorithms that are “obviously correct” fail this kind of check surprisingly often, and the failing input is usually tiny enough to reason about by hand.

Two details keep such a harness honest. Generate random inputs with duplicate values, because many subtle bugs only appear when ties exist — and next_permutation enumerates tie-containing inputs correctly without extra code. And keep the brute force deliberately naive: if you optimize the oracle with pruning, you risk building the same wrong assumption into both sides of the comparison.

---

Checklist for correct enumeration

• Sort with the same comparator (or projection) that you pass to next_permutation.
• Use do/while so the first arrangement is processed.
• Don’t break out and then assume the range is sorted. It stays in whatever permutation you stopped at.
• For k-permutations, reverse the suffix after each use.
• For combinations, permute a selector.

---

Related Articles

• C++ STL Algorithms Overview
• C++ std::sort and Custom Comparators
• C++ std::reverse
• C++ Bit Manipulation
• C++ Heap Algorithms