C++ Basics: Enumerate Distinct Arrangements from Sorted Input

Use std::next_permutation to visit arrangements of a short sequence with repeated values.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as next-permutation-enumeration-demo.cpp:

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

int main()
{
    std::vector<int> values{1, 1, 2};
    int count = 0;
    do {
        for (int value : values) std::cout << value;
        std::cout << '\n';
        ++count;
    } while (std::next_permutation(values.begin(), values.end()));
    std::cout << "Arrangements: " << count << '\n';
    std::cout << "Reset:";
    for (int value : values) std::cout << ' ' << value;
    std::cout << '\n';
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic next-permutation-enumeration-demo.cpp -o next-permutation-enumeration-demo &&
./next-permutation-enumeration-demo

Observed output:

112
121
211
Arrangements: 3
Reset: 1 1 2

Read the result

Starting in ascending order visits 112, 121, and 211 exactly once. When there is no larger arrangement, next_permutation returns false and restores the first arrangement. The do-while loop prints the initial arrangement before asking for its successor.

Apply it carefully

Sort the initial range with the same comparator if you intend to enumerate all arrangements. Starting in the middle only visits the remaining suffix of lexicographic order. Repeated equivalent values reduce the number of distinct arrangements, but growth can still be factorial. This is useful for small exhaustive tests, not a scalable search strategy for large collections.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- next-permutation-enumeration-demo.cpp next-permutation-enumeration-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.