【C++】std::next_permutation ですべての順列を生成する方法

2025年8月31日

はじめに

プログラミングでは、{A, B, C} という要素の集まりから、{A, C, B}, {B, A, C}, {B, C, A} といった、考えられる全ての並び順（順列）をリストアップしたい場面があります。

C++の標準ライブラリ <algorithm> には、この順列生成を簡単に行うための std::next_permutation という便利な関数が用意されています。この関数は、現在の並び順を、辞書順で「次の」順列に並べ替えてくれます。

この記事では、next_permutation と do-while ループを組み合わせて、コンテナの全順列を網羅的に列挙する、定石的なテクニックを解説します。

`next_permutation` を使ったサンプルコード

このコードは、{'A', 'B', 'C'} という3つの文字が格納された vector の、全ての順列を標準出力に出力します。

完成コード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // next_permutation を使うために必要

using namespace std;

int main() {
    vector<char> elements = {'A', 'B', 'C'};
    
    // 1. 最初の順列を出力
    cout << "--- 全ての順列 ---" << endl;
    
    // 2. do-whileループとnext_permutationで全順列を列挙
    do {
        for (char c : elements) {
            cout << c << " ";
        }
        cout << endl;
    } while (next_permutation(elements.begin(), elements.end()));
    
    return 0;
}

実行結果

--- 全ての順列 ---
A B C 
A C B 
B A C 
B C A 
C A B 
C B A

コードの解説

`std::next_permutation(elements.begin(), elements.end())`

これが、順列を生成する核心部分です。

next_permutation: <algorithm> ヘッダーで提供される関数です。
引数: 第1引数に範囲の開始イテレータ (elements.begin()) を、第2引数に範囲の終了イテレータ (elements.end()) を取ります。
動作:
- 引数で指定された範囲 (elements全体) を、現在の並び順の辞書順で次の並び順に並べ替えます。
- もし次の順列が存在すれば（並べ替えに成功すれば）、true を返します。
- もし現在の順列が既に辞書順で最後（この例では C B A）であれば、範囲を最初の順列（A B C）に戻し、false を返します。

`do-while` ループとの組み合わせ

next_permutation は、do-while ループと組み合わせるのが定石です。

最初に、do ブロックの中が実行され、ソート済みの初期状態（A B C）がまず出力されます。
while の条件式で next_permutation が呼ばれ、elements が次の順列（A C B）に並べ替えられ、true が返るため、ループが続行します。
これを繰り返し、elements が最後の順列 C B A になった状態で next_permutation が呼ばれると、elements は最初の順列 A B C に戻り、関数は false を返します。これにより、while の条件が満たされなくなり、ループが綺麗に終了します。