順列組合せ (重複有り無し) を生成するライブラリ 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(); を使えば，DLOG に渡せる．

忘れやすい利用シーン

ボールと仕切りの重複組合せ

区別されない $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] 個入っている
}