第59回 順列・シャッフル系アルゴリズム
next_permutation（辞書順の次の並び）、shuffle（ランダム並び替え）、sample（ランダム抽出）。順列全列挙やランダム化に。
1. 一覧
| 関数 | 用途 |
|---|
std::next_permutation | 辞書順で次の順列に（最後なら false） |
std::prev_permutation | 辞書順で前の順列に |
std::is_permutation | 別の範囲が順列になっているか |
std::shuffle | ランダムに並べ替え (C++11～) |
std::sample | n 要素をランダム抽出 (C++17) |
注意： C++17 で std::random_shuffle は非推奨、C++17 で削除されました。std::shuffle + 乱数エンジン を使います。
2. next_permutation ― 辞書順の次
全順列を列挙useful
std::vector<int> v = {1,2,3};
do {
// v を出力
for (int x : v) std::cout << x << " ";
std::cout << "\n";
} while (std::next_permutation(v.begin(), v.end()));
// 出力:
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1
前提： 入力がソート済み（最小の順列）から始めれば、すべての順列を 1 回ずつ通ります。
3. shuffle ― ランダム化
shuffleC++11～
#include <algorithm>
#include <random>
std::vector<int> v = {1,2,3,4,5};
std::random_device rd;
std::mt19937 gen(rd()); // メルセンヌ・ツイスタ
std::shuffle(v.begin(), v.end(), gen);
// v がランダムに並び替わる
4. sample ― ランダム抽出 (C++17)
sampleC++17
std::vector<int> v = {1,2,3,4,5,6,7,8,9,10};
std::vector<int> picked;
std::sample(v.begin(), v.end(),
std::back_inserter(picked),
3,
std::mt19937{std::random_device{}()});
// picked に 3 個がランダム抽出される（順序は維持）
「10 個から 3 個を抽選」のような処理が 1 行で書けます。
確認クイズ
Q1. std::next_permutation で全順列を列挙するための前提は？
任意の初期順序
ソート済み（最小順列）から始める
逆順から始める
重複なし
ソート済みから始めて do-while で次へ、全パターンを巡ります。
Q2. std::shuffle に必要な引数は？
範囲だけ
範囲 + 乱数エンジン
範囲 + シード値
範囲 + 比較関数
C++11 以降、shuffle には明示的な乱数エンジン（mt19937 等）を渡します。random_shuffle は C++17 で削除。
Q3. 配列から 5 個をランダム抽出するのは？
std::shuffle して先頭 5 個
std::random_shuffle
std::sample
std::sort
C++17 の std::sample がダイレクト。shuffle + 先頭 n 個でも同等ですが、sample のほうが意図が明確。
Q4. C++17 で削除された関数は？
std::shuffle
std::next_permutation
std::random_shuffle
std::sample
random_shuffle は C の rand() を暗黙に使っていたため、C++11 で非推奨、C++17 で削除。代わりに乱数エンジンを明示する std::shuffle を使います。