What is Permutation Algorithms in C++?

Generate and enumerate lexicographic permutations, check range equivalence, and randomly shuffle sequences using the C++ Standard Library.

Which C++ standard introduced Permutation Algorithms?

Permutation Algorithms was introduced in C++98.

What is the difficulty level of Permutation Algorithms?

Permutation Algorithms is considered Intermediate-level C++ material.

Permutation Algorithms

Permutation Algorithmssince C++98

A family of standard library algorithms that generate successive lexicographic permutations of a range in-place, test whether two ranges contain the same elements in any order, and randomly reorder elements using a uniform random bit generator.

Overview

Four algorithms form the permutation family:

std::next_permutation / std::prev_permutation (C++98): Transform a range in-place into its lexicographically next or previous permutation. Each returns false the moment the sequence wraps around — next_permutation resets to the smallest (ascending-sorted) permutation, prev_permutation to the largest (descending-sorted).
std::is_permutation (C++11): Determine whether two ranges are rearrangements of each other without requiring either to be sorted.
std::shuffle (C++11): Randomly reorder elements using a caller-supplied uniform random bit generator (URBG). Replaces std::random_shuffle, which was deprecated in C++14 and removed in C++17 due to its dependence on the low-quality std::rand.

All four gained std::ranges:: counterparts in C++20, which accept range objects and projections in place of raw iterator pairs and comparators.

Syntax

cpp

Godbolt

// next_permutation — C++98; bidirectional iterators required
template<class BidirIt>
bool std::next_permutation(BidirIt first, BidirIt last);

template<class BidirIt, class Compare>
bool std::next_permutation(BidirIt first, BidirIt last, Compare comp);

// prev_permutation — C++98
template<class BidirIt>
bool std::prev_permutation(BidirIt first, BidirIt last);

template<class BidirIt, class Compare>
bool std::prev_permutation(BidirIt first, BidirIt last, Compare comp);

// is_permutation — C++11; forward iterators sufficient
template<class ForwardIt1, class ForwardIt2>
bool std::is_permutation(ForwardIt1 first1, ForwardIt1 last1,
                          ForwardIt2 first2);

// four-iterator overload — C++14 (size-checks before element comparison)
template<class ForwardIt1, class ForwardIt2>
bool std::is_permutation(ForwardIt1 first1, ForwardIt1 last1,
                          ForwardIt2 first2, ForwardIt2 last2);

template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
bool std::is_permutation(ForwardIt1 first1, ForwardIt1 last1,
                          ForwardIt2 first2, BinaryPredicate p);

// shuffle — C++11; random access iterators required
template<class RandomIt, class URBG>
void std::shuffle(RandomIt first, RandomIt last, URBG&& g);

// Ranges equivalents — all C++20
auto std::ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {});
auto std::ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
bool std::ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {}, Proj1 p1 = {}, Proj2 p2 = {});
void std::ranges::shuffle(R&& r, URBG&& g);

Examples

Enumerating all permutations

To visit every permutation exactly once, sort the range first. next_permutation returns false precisely when it cycles back to sorted order, making a do/while the natural control structure.

cpp

Godbolt

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

void enumerate_all() {
    std::vector<int> v = {1, 2, 3};
    std::sort(v.begin(), v.end());  // mandatory: start from lexicographic minimum

    do {
        for (int x : v) std::cout << x << ' ';
        std::cout << '\n';
    } while (std::next_permutation(v.begin(), v.end()));
    // prints all 3! = 6 permutations in lexicographic order
    // v is back to {1, 2, 3} after the loop
}

Calling next_permutation on an unsorted range produces only the permutations that are lexicographically greater than the starting arrangement — the rest are silently skipped.

Custom comparator for structured types

The comparator overload redefines what "lexicographic order" means. The same comparator must be passed to both the initial sort and the permutation call; mixing them produces meaningless traversal order.

cpp

Godbolt

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

struct Job { int priority; std::string name; };

void schedule_permutations() {
    std::vector<Job> jobs = {{3, "build"}, {1, "test"}, {2, "deploy"}};

    auto by_priority = [](const Job& a, const Job& b) {
        return a.priority < b.priority;
    };

    std::sort(jobs.begin(), jobs.end(), by_priority);

    do {
        for (const auto& j : jobs) std::cout << j.name << ' ';
        std::cout << '\n';
    } while (std::next_permutation(jobs.begin(), jobs.end(), by_priority));
}

Checking permutation equivalence

std::is_permutation answers "do these two ranges contain the same multiset of elements?" without sorting either. The four-iterator form (C++14) short-circuits immediately when the ranges differ in size.

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <cassert>

void verify_equivalence() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {3, 1, 4, 5, 2};
    std::vector<int> c = {1, 2, 3, 4, 6};

    // Prefer the four-iterator overload — avoids unsafe length assumption
    assert( std::is_permutation(a.begin(), a.end(),
                                 b.begin(), b.end()));   // true  — C++14
    assert(!std::is_permutation(a.begin(), a.end(),
                                 c.begin(), c.end()));   // false — C++14

    // Custom equality predicate: case-insensitive string comparison
    std::vector<std::string> x = {"Hello", "World"};
    std::vector<std::string> y = {"world", "hello"};
    auto icase_eq = [](const std::string& p, const std::string& q) {
        return std::equal(p.begin(), p.end(), q.begin(), q.end(),
                          [](char a, char b){ return std::tolower(a) == std::tolower(b); });
    };
    assert(std::is_permutation(x.begin(), x.end(), y.begin(), y.end(), icase_eq));
}

is_permutation runs in O(n²) for unsorted input. When both ranges are sorted, std::equal after sorting is O(n log n + n) and far faster for large n.

Shuffling with a seeded Mersenne Twister

cpp

Godbolt

#include <algorithm>
#include <random>
#include <numeric>
#include <vector>

std::vector<int> make_shuffled_deck(int n) {
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 1);           // C++11: fill 1..n

    std::mt19937 rng(std::random_device{}());   // C++11: hardware-seeded PRNG
    std::shuffle(v.begin(), v.end(), rng);      // C++11

    return v;
}

Construct the engine outside any loop. Re-constructing std::mt19937 from the same seed inside a loop produces identical shuffle sequences on every iteration.

C++20 Ranges — projections and result structs

std::ranges::next_permutation returns a ranges::in_found_result<I> carrying the past-the-end iterator and a found flag, replacing the bool return with a named-field struct. Projections eliminate the need for a full comparator when you only need to key on a member.

cpp

Godbolt

#include <algorithm>
#include <ranges>
#include <vector>
#include <cstdlib>
#include <iostream>

void ranges_example() {                                             // C++20
    std::vector v = {1, 2, 3};
    std::ranges::sort(v);

    do {
        for (int x : v) std::cout << x << ' ';
        std::cout << '\n';
    } while (std::ranges::next_permutation(v).found);

    // Permute by absolute value via projection — no explicit comparator needed
    std::vector<int> w = {-3, 1, -2};
    auto abs_proj = [](int x){ return std::abs(x); };
    std::ranges::sort(w, {}, abs_proj);

    do {
        for (int x : w) std::cout << x << ' ';
        std::cout << '\n';
    } while (std::ranges::next_permutation(w, {}, abs_proj).found);
}

Best Practices

Sort before enumerating. next_permutation only generates permutations lexicographically greater than the current state. An unsorted starting point silently skips all smaller permutations.

Use the four-iterator is_permutation overload (C++14). The three-iterator form assumes [first2, first2 + distance(first1, last1)) is a valid range — an assumption that is silently violated whenever the second container is shorter, triggering undefined behaviour.

Prefer std::mt19937 seeded via std::random_device. std::random_shuffle was removed in C++17 precisely because std::rand has non-uniform distributions and implementation-defined seeding. std::mt19937 is portable, fast, and has a 19937-bit period.

Fall back to sort + std::equal for large-scale permutation checks. is_permutation's O(n²) complexity is acceptable for n up to a few thousand; beyond that, sort copies of both ranges and compare with std::equal.

Common Pitfalls

Forgetting to sort before next_permutation. This is by far the most common misuse — you enumerate a suffix of the permutation space and never know it.

Reusing a fixed-seed engine across independent shuffles. std::mt19937 rng(42) constructed inside a loop resets to the same state every iteration, producing identical output. Construct once and reuse, or reseed from std::random_device each time if independence is required.

Mixing comparators between sort and permutation. The permutation algorithms define lexicographic order through the comparator. Using std::sort with comparator A and std::next_permutation with comparator B produces traversal in a meaningless order without any diagnostic.

Misreading the false return as "no permutation generated". next_permutation returns false after it wraps back to sorted order — it still modifies the range. The false means "we cycled"; the range is now the lexicographic minimum, not unchanged.

Applying shuffle to forward-iterator containers. std::shuffle requires random access iterators. std::list, std::deque (which supports random access but rarely performantly), and std::set need to be copied into a std::vector first.

Ranking and Unranking Permutations (Lehmer Code)

Every permutation of n distinct elements has a unique rank in lexicographic order, from 0 (sorted ascending) to n!−1 (sorted descending). The Lehmer code encodes that rank as a mixed-radix number: for each position i, count how many elements to the right of position i are smaller than v[i], then multiply by (n−i−1)!.

cpp

Godbolt

#include <vector>
#include <numeric>
#include <stdexcept>

// Returns the 0-based lexicographic rank of permutation v.          // C++11
long long permutation_rank(std::vector<int> v) {
    int n = static_cast<int>(v.size());
    long long rank = 0, fact = 1;
    for (int i = n - 2; i >= 0; --i) {
        int smaller = 0;
        for (int j = i + 1; j < n; ++j)
            if (v[j] < v[i]) ++smaller;
        rank += smaller * fact;
        fact *= (n - i - 1);
    }
    return rank;
}
// {2, 0, 1}  →  rank 3
// {0, 1, 2}  →  rank 0
// {2, 1, 0}  →  rank 5  (= 3!−1)

The inverse operation reconstructs the permutation from its rank by stripping off factorial-weighted digits one at a time.

cpp

Godbolt

// Returns the permutation of {0, 1, ..., n-1} at 0-based rank r.   // C++11
std::vector<int> permutation_at_rank(int n, long long r) {
    std::vector<int> available(n);
    std::iota(available.begin(), available.end(), 0);

    std::vector<int> result;
    result.reserve(n);

    // precompute factorials
    std::vector<long long> fact(n, 1);
    for (int i = 1; i < n; ++i) fact[i] = fact[i-1] * i;

    for (int i = n - 1; i >= 0; --i) {
        long long idx = r / fact[i];
        r %= fact[i];
        result.push_back(available[static_cast<int>(idx)]);
        available.erase(available.begin() + idx);
    }
    return result;
}
// permutation_at_rank(3, 3)  →  {2, 0, 1}
// permutation_at_rank(3, 0)  →  {0, 1, 2}

Use Lehmer coding when you need to store or transmit a permutation as a single integer. A permutation of 20 elements fits in a 64-bit integer (20! ≈ 2.4 × 10¹⁸ < 2⁶⁴), saving memory over a full array when the element count is known statically.

Partial Permutations (P(n,r))

A partial permutation P(n,r) selects r items from n and arranges them in order: there are n! / (n−r)! such arrangements. For example, P(5,3) = 5×4×3 = 60. std::next_permutation permutes an entire range, so the cleanest approach is to permute the full range and project onto the first r positions.

cpp

Godbolt

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

// Generate all distinct ordered r-tuples from v.                    // C++14
void partial_permutations(std::vector<int> v, int r) {
    std::sort(v.begin(), v.end());

    std::set<std::vector<int>> seen;
    do {
        std::vector<int> front(v.begin(), v.begin() + r);
        if (seen.insert(front).second) {
            for (int x : front) std::cout << x << ' ';
            std::cout << '\n';
        }
    } while (std::next_permutation(v.begin(), v.end()));
    // P(5,3) = 60 lines for v = {1,2,3,4,5}, r = 3
}

Deduplication via a std::set is only needed when the input contains duplicates. For a fully distinct input, every full permutation produces a distinct front slice — the seen guard is unnecessary overhead and can be removed.

The total number of full permutations visited is n!, but only the first r positions differ meaningfully between consecutive calls. For large n with small r, consider a recursive generator that avoids producing the tail.

cpp

Godbolt

// Recursive generator: avoids generating the n-r suffix entirely.  // C++11
void gen_partial(std::vector<int>& v, int r, int depth) {
    if (depth == r) {
        for (int i = 0; i < r; ++i) std::cout << v[i] << ' ';
        std::cout << '\n';
        return;
    }
    for (int i = depth; i < static_cast<int>(v.size()); ++i) {
        std::swap(v[depth], v[i]);
        gen_partial(v, r, depth + 1);
        std::swap(v[depth], v[i]);
    }
}
// Call with gen_partial(v, r, 0); — produces P(n,r) lines.

Multiset Permutations (Duplicates)

When the input contains repeated elements, std::next_permutation automatically skips arrangements that are logically identical, generating exactly n! / (k₁! × k₂! × … × kₘ!) distinct permutations for a multiset with repetition counts k₁, k₂, …, kₘ.

cpp

Godbolt

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

void multiset_permutations() {                                       // C++98
    std::vector<int> v = {1, 1, 2};
    std::sort(v.begin(), v.end());  // must start from lexicographic minimum

    int count = 0;
    do {
        for (int x : v) std::cout << x << ' ';
        std::cout << '\n';
        ++count;
    } while (std::next_permutation(v.begin(), v.end()));
    // Prints exactly 3 permutations: {1,1,2}, {1,2,1}, {2,1,1}
    // count == 3  (= 3! / 2! = 3, not 6)
}

The same logic applies to custom comparators: two elements are considered equal when neither comp(a,b) nor comp(b,a) is true. Permutations that differ only by swapping those equivalent elements are collapsed into one.

cpp

Godbolt

// Verify with is_permutation across duplicated values.              // C++14
#include <cassert>

void verify_multiset_identity() {
    std::vector<int> a = {1, 1, 2};
    std::vector<int> b = {1, 2, 1};   // same multiset, different order
    assert(std::is_permutation(a.begin(), a.end(),
                               b.begin(), b.end()));   // true
}

std::is_permutation handles duplicates correctly without any extra logic. It counts element occurrences using the supplied equality predicate, so {1,1,2} and {2,1,1} are correctly identified as the same multiset even though their element counts include repeats.

Fisher-Yates / Knuth Shuffle Internals

std::shuffle implements the modern Fisher-Yates algorithm: iterate from the last position down to position 1, and at each position i swap the element there with a uniformly chosen element from positions 0 through i (inclusive). This single-pass, O(n) algorithm generates every permutation with equal probability 1/n!.

cpp

Godbolt

#include <algorithm>
#include <random>
#include <numeric>
#include <vector>
#include <iostream>

// Equivalent to std::shuffle — shown for clarity.                   // C++11
void fisher_yates_manual(std::vector<int>& v, std::mt19937& rng) {
    for (int i = static_cast<int>(v.size()) - 1; i > 0; --i) {
        std::uniform_int_distribution<int> dist(0, i);
        std::swap(v[i], v[dist(rng)]);
    }
}

Never substitute v[i] = v[rand() % n] for the Fisher-Yates swap. Picking a random position independently for each element produces n^n possible outcome sequences, not n!. Many permutations become unreachable or appear at systematically skewed frequencies.

You can verify uniformity empirically: shuffle a small array many times and confirm each permutation appears with the expected frequency.

cpp

Godbolt

#include <map>

void verify_shuffle_uniformity() {                                   // C++11
    std::vector<int> base = {1, 2, 3};
    std::map<std::vector<int>, int> freq;

    std::mt19937 rng(42);  // deterministic seed for reproducibility
    constexpr int trials = 60'000;
    for (int i = 0; i < trials; ++i) {
        auto v = base;
        std::shuffle(v.begin(), v.end(), rng);
        ++freq[v];
    }
    // Each of the 3! = 6 permutations should appear ~10000 times.
    // Any permutation with frequency far outside [9000, 11000] signals bias.
    for (const auto& [perm, count] : freq) {
        for (int x : perm) std::cout << x << ' ';
        std::cout << "→ " << count << '\n';
    }
}

Use std::random_device{}() to seed for non-reproducible shuffles; use a fixed seed like mt19937 rng(42) for reproducible tests. The two use cases are distinct: production code typically wants entropy, test code wants determinism.

Performance Analysis

All permutation algorithms operate in-place and require no heap allocation — auxiliary space is O(1).

Algorithm	Time per call	Total for all n! perms	Iterator requirement	Mutates range
`next_permutation`	O(n) worst, O(1) amortized	O(n × n!)	Bidirectional	Yes
`prev_permutation`	O(n) worst, O(1) amortized	O(n × n!)	Bidirectional	Yes
`is_permutation` (unsorted)	O(n²)	—	Forward	No
`is_permutation` (pre-sorted)	O(n log n + n) via sort+equal	—	Forward	No (sort copy)
`shuffle`	O(n)	—	Random access	Yes

The amortized O(1) per-call claim for next_permutation follows from the total work across all n! permutations being O(n × n!), divided by n! calls. In the worst case (the last permutation before wraparound), it performs O(n) comparisons and swaps.

cpp

Godbolt

// is_permutation: O(n²) vs O(n log n) crossover.                   // C++17
#include <algorithm>
#include <vector>

bool fast_is_permutation(std::vector<int> a, std::vector<int> b) {
    if (a.size() != b.size()) return false;
    std::sort(a.begin(), a.end());   // O(n log n)
    std::sort(b.begin(), b.end());   // O(n log n)
    return a == b;                   // O(n)
    // Prefer for n > ~5000 where O(n²) becomes measurable.
}

Prefer sort + std::equal over std::is_permutation when n exceeds a few thousand. The crossover point is workload-dependent, but for typical integer comparisons the sort-based approach dominates above roughly n = 5000.

C++20 Ranges Composition

The std::ranges:: variants of the permutation algorithms integrate cleanly with range adaptors, eliminating raw iterator pairs and enabling expressive pipelines.

std::ranges::next_permutation returns an in_found_result<I> struct rather than a bare bool. The .found field carries the same boolean semantics as the classic return value — it is false when the range has wrapped around to sorted order.

cpp

Godbolt

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

void ranges_count_permutations() {                                   // C++20
    std::vector v = {1, 2, 3, 4};
    std::ranges::sort(v);

    long long count = 0;
    do {
        ++count;
    } while (std::ranges::next_permutation(v).found);
    // count == 24  (= 4!)
    // No storage of intermediate permutations required.
}

Combine views::take with the permutation loop to project onto the first k elements of each arrangement.

cpp

Godbolt

void ranges_take_prefix() {                                          // C++20
    std::vector v = {1, 2, 3, 4};
    std::ranges::sort(v);

    do {
        // View first 2 elements of the current permutation.
        for (int x : v | std::views::take(2))
            std::cout << x << ' ';
        std::cout << '\n';
    } while (std::ranges::next_permutation(v).found);
}

Filter permutations by a predicate without storing all of them first — check the condition inline within the loop body.

cpp

Godbolt

void ranges_filter_permutations() {                                  // C++20
    std::vector v = {1, 2, 3, 4};
    std::ranges::sort(v);

    int qualifying = 0;
    do {
        // Keep only permutations where the sum of the first 2 elements > 4.
        auto prefix = v | std::views::take(2);
        int s = 0;
        for (int x : prefix) s += x;
        if (s > 4) ++qualifying;
    } while (std::ranges::next_permutation(v).found);
    // qualifying == number of permutations of {1,2,3,4} with v[0]+v[1] > 4
}

std::ranges::shuffle accepts a range directly and forwards to the same Fisher-Yates implementation as the iterator-pair overload.

cpp

Godbolt

void ranges_shuffle_example() {                                      // C++20
    std::vector v = {1, 2, 3, 4, 5};
    std::mt19937 rng(std::random_device{}());
    std::ranges::shuffle(v, rng);  // identical semantics to std::shuffle
}

Check .found rather than negating it. The found field is true while more permutations exist — the loop continues as long as found is true, making while (std::ranges::next_permutation(v).found) the idiomatic form, analogous to while (std::next_permutation(...)).