順列組合せ

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

使用例

IntPerm ip(10, 3);   // 10 から 3 とる順列
while (ip.get()) {
  for (int i = 0; i < 10; i++) cout << ip[i] << " ";
}

struct

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

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

最初の4つは，$[0, m)$ の数からなる長さ $n$ のリストを生成する．このライブラリでは，「順列」と「組合せ」の違いは，後者は昇順にソートされている，ということである．

IntPerm(m, n)

$[0, m)$ から $n$ 個とる順列．全部で $m! / (m - n)!$ 個．
$[0, m)$ からなる長さ $n$ のリストで，同じ数がたかだか1回しか現れないものを列挙する．

たとえば IntPerm(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(m, n)

$[0, m)$ から $n$ 個とる組合せ．全部で $\displaystyle\binom{m}{n}$ 個．
$[0, m)$ からなる長さ $n$ のリストで，同じ数がたかだか1回しか現れず，昇順ソートされているものを列挙する．
たとえば，IntComb(4, 2) は，次を生成する:
```
[0,1], [0,2], [0,3], [0,4], [1,2], [1,3], [2,3]
```

IntDupPerm(m, n)

$[0, m)$ から $n$ 個とる重複順列．全部で $m^n$ 個．
$[0, m)$ からなる長さ $n$ のリストを列挙する．

たとえば idp(3, 2) は，次を生成する:

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

IntDupComb(m, n)

$[0, m)$ から $n$ 個とる重複組合せ．全部で $\displaystyle\binom{m + n - 1}{n}$ 個．
- あるいは，$n$ 個のボールを $m$ 個の箱に入れる方法．箱ごとのボールの数の組合せの列挙は，後述してある．
$[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(vector{m1, m2, …})

直積 $[0, m_1) \times [0, m_2) \times \dots \times [0, m_n]$．全部で $\prod_{i=1}^{n} m_i$ 個．
上の直積の要素を列挙する．
たとえば，IntDirProd(vector{1, 2, 3}) は，次を生成する:
```
[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2]
```

IntPartition(n)

$n$ の分割．
$n$ の分割の要素を列挙する．

たとえば，IntPartition(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] 個入っている
}

Python での計算

考察時に，だいたいのサイズを知りたいことがある．Python では次のように計算できる．

from math import factorial, perm, comb 
print(perm(m, n))         # IntPerm(m, n)
print(comb(m, n))         # IntComb(m, n)
print(m ** n)             # IntDupPerm(m, n)
print(comb(m + n - 1, n)) # IntDupComb(m, n)
print(factorial(n))       # n!

分割数

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)

キーワード: permutation, combination, duplicate permutation, duplicate combination, binom, partition, direct product

使用例#

struct#

IntPerm(m, n)#

IntComb(m, n)#

IntDupPerm(m, n)#

IntDupComb(m, n)#

IntDirProd(vector{m1, m2, …})#

IntPartition(n)#

生成#

注意1#

注意2#

デバッグ用#

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

その他#

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

Python での計算#

分割数#

使用例