この記事のオリジナル は，2023年2月28日に公開されました．
競技プログラミング用の，順列組合せ (重複有り無し) を生成する自作 C++ ライブラリ Perm の使用法です．ソースコードはここ にあります．
struct
4つの struct がある．名前がおかしいのは歴史的理由による．
- IntPerm 順列
- IntComb 組合せ
- IntDupPerm 重複順列
- IntDupComb 重複組合せ
constructor
IntPerm ip(m, n);
IntComp ic(m, n);
IntDupPerm idp(m, n);
IntDupComb idc(m, n);
これらはいずれも，$[0, m)$ の数からなる長さ $n$ のリストを生成する．
このライブラリでは，「順列」と「組合せ」の違いは，後者は昇順にソートされている，ということである．
IntPerm
$[0, m)$ からなる長さ $n$ のリストで，同じ数がたかだか1回しか現れないものを列挙する．
たとえば ip(4, 2) は，次を生成する:
[0,1], [0,2], [0,3], [0,4], [1,0], [1,1], [1,2], [1,3], [2,0], [2,1], [2,2], [2,3], [3,0], [3,1], [3,2], [3,3]
IntComb
$[0, m)$ からなる長さ $n$ のリストで，同じ数がたかだか1回しか現れず，昇順ソートされているものを列挙する．
たとえば，ic(4, 2) は，次を生成する:
[0,1], [0,2], [0,3], [0,4], [1,2], [1,3], [2,3]
IntDupPerm
$[0, m)$ からなる長さ $n$ のリストを列挙する．
たとえば idp(4, 2) は，次を生成する:
[0,0], [0,1], [0,2], [0,3], [1,0], [1,1], [1,2], [1,3], [2,0], [2,1], [2,2], [2,3], [3,0], [3,1], [3,2], [3,3]
IntDupComb
$[0, m)$ からなる長さ $n$ のリストで，昇順ソートされているものを列挙する．
たとえば idc(4, 2) は，次を生成する:
[0,0], [0,1], [0,2], [0,3], [1,1], [1,2], [1,3], [2,2], [2,3], [3,3]
生成
obj.get() が true を返す間，新しいリストが生成される．リストの i 番目の要素は，obj.at() である．
while (ip.get()) {
for (int i = 0; i < 2; i++) cout << ip.at(i) << " ";
}
注意1
obj.get() が false を返すときには，内部状態は初期値に戻るので，そのまま次のラウンドを実行することができる．
注意2
- $n \geq 0, r \geq 0$ でないときには，何も生成しない．
- IntPerm と IntComb は，$r \leq n$ でないときには，何も生成しない．
- IntDupPerm と IntDupComb は，$n = r = 0$ のときに，何も生成しないのでは なく，空リスト
[]を生成する．これは，ことによると適切でないかもしれない．($0^0 = 1$ になるし，$H(n, r) \neq C(n+r-1, r)$ になるから) - $n = 0$ かつ $r \neq 0$ の場合には，何も生成しない．
デバッグ用
const vector<int>& obj.vec_view(); でベクトルに変換できる．
忘れやすい利用シーン
ボールと仕切りの重複組合せ
区別されない $a$ 個のボールを 区別される $b$ 個の箱に入れる方法は，IntDupComb(b, a) が列挙するリストと対応付けられる．リスト $[x_1, ..., x_a]$ は，ボール $1$ が箱 $x_1$に，ボール $2$ が箱 $x_2$に，..., ボール $a$ が箱 $x_a$ に入っていることを意味している．(ボールを区別しないことは，入る箱を昇順にして良いことと対応している．) したがって，各箱に入っているボールの数は，次のように求められる．
IntDupComb idc(b, a);
while (idc.next()) {
vector<ll> numBalls(b);
REP(i, 0, a) numBalls[idc.at(i)]++;
// 箱 j にはボールが numBalls[j] 個入っている
}