順列組合せ

競技プログラミング用の，順列組合せ (重複有り無し) を生成する自作 C++ ライブラリ Perm の使用法です．ソースコードはここにあります．

struct

以下の struct がある．名前がおかしいのは歴史的理由による．

IntPerm 順列
IntComb 組合せ
IntDupPerm 重複順列
IntDupComb 重複組合せ
IntDirProd 直積
IntPartition 分割数

constructor

IntPerm ip(m, n);         // m から n 取る順列
IntComp ic(m, n);         // m から n 取る組合せ
IntDupPerm idp(m, n);     // m から n 取る重複順列
IntDupComb idc(m, n);     // m から n 取る重複組合せ
IntDirProd did(vector<int>{{m1, m2, ...}})   // [0:m1) × [0:m2) × ...
IntPartition part(m)      // m の分割

最初の4つは，$[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]

後述の「ボールと箱の重複組合せ」も参照のこと．

IntDirProd

$[0, m_1) \times [0, m_2) \times \dots$ の要素を列挙する．たとえば，did(vector{{1, 2, 3}}) は，次を生成する:

[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2]

IntPartition

分割を生成する．たとえば，part(5) は，次を生成する．

[[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]

生成

obj.get() が true を返す間，新しいリストが生成される．リストの i 番目の要素は，obj.at(i) である．obj[i] でも良い．

while (ip.get()) {
  for (int i = 0; i < 2; i++) cout << ip.at(i) << " ";
}

主としてデバッグ用に，obj.vec_view() も用意されており，const vector<int>& を返す．

const vector<int>& v = ip.vec_view();
for (int i = 0; i < 2; i++) cout << v[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(); でベクトルに変換できる．

`[0, 1, ..., n)` 以外の対象

コンストラクタの第3引数に，長さ $m$ のベクトルを置いて，そこから取ってこさせることができる:

  IntComb ip(4, 2, vector{{100, 50, 90, 10}});
  // [[100, 50], [100, 90], [100, 10], [50, 90], [50, 10], [90, 10]]
  IntPerm<char> ip(3, 2, vector<char>{'a', 'b', 'c'});
  // [['a', 'b'], ['a', 'c'], ['b', 'a'], ['b', 'c'], ['c', 'a'], ['c', 'b']]

メソッド set_mapping を使うこともできる．

  IntPerm<char> ip(3, 2);
  ip.set_mapping([](int i) { return "abc"[i]; });
  // 上と同じ

その他

ボールと箱の重複組合せ

区別される $m$ 個の箱があって，そこに区別されない $n$ 個のボールを入れることを考える状況がよくある．これは，$m$ から重複を許して $n$ だけ選ぶ，ということになる．たとえば，$m = 3$ 個の箱 A, B, C があって，そこに $n = 5$ 個のボールをいれて，おのおの 2個，1個，2個入った，ケースを考えよう．これは，このライブラリで言えば，箱 A, B, C に識別番号 0, 1, 2 がついていて，5回の選択で [0, 0, 1, 2, 2] が選ばれた，ということに対応している．

しかし，このような状況では，普通，各々の箱にボールがいくつあるか，ということに興味があろう．上のケースでは [2, 1, 2] を生成してほしいわけである．これは，次のコードで可能になる:

IntDupComb idc(m, n);
while (idc.get()) {
  vector<ll> numBalls(m);
  REP(i, 0, n) numBalls[idc.at(i)]++;
  //  箱 j にはボールが numBalls[j] 個入っている
}

分割数

10000 までの分割数の表は，https://oeis.org/A000041/b000041.txt にある．
最初のほうのいくつかは次の通り:

// 0  1  2  3  4  5   6   7   8   9  10  11  12   13   14   15   16   17   18   19    //  i
[  1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490]   // p(i)
p(20) = 627
p(25) = 1958
p(30) = 5604
p(40) = 37338 (3.7E4)
p(50) = 204226 (2.0E5)
p(61) = 1121505 (1.1E6)
p(77) = 10619863 (1.1E7)

struct#

constructor#

IntPerm#

IntComb#

IntDupPerm#

IntDupComb#

IntDirProd#

IntPartition#

生成#

注意1#

注意2#

デバッグ用#

[0, 1, ..., n) 以外の対象#

その他#

ボールと箱の重複組合せ#

分割数#