bitによる部分集合の列挙 と 数学的理解
bitテクニックで、集合の部分集合を列挙するものがあります。その紹介と数学的理解です。
bitによる部分集合の列挙
集合uint S
に対して、S
の部分集合T
は次のようにして全列挙できます。
uint S; // <- 集合 for (uint T=S; ; T=(T-1)&S) { // 処理 if (T==0) break; }
例えばS
が0b100101
のときは、T
はfor
の中で、0b100101
0b100100
0b100001
0b100000
0b101
0b100
0b1
0b0
の順に変化します。
ちゃんとS
の部分集合すべてが降順で列挙できてることがわかります。
ちなみにこのテクニックは蟻本に載ってました。
何がうれしいの
大きさn
の集合S
と、S
の部分集合T
を全列挙しようとしたときに単純な実装だと次のようになります。
for(uint S=0; S<1<<n; S++) { for(uint T=0; T<1<<n; T++) { if ((T&S) != T) continue; // 処理 } }
これだと全体の計算量は になりますが、上述のbitテクニックを使うと
for(uint S=0; S<1<<n; S++) { for (uint T=S; ; T=(T-1)&S) { // 処理 if (T==0) break; } }
となり になります。なぜなら、S
とT
の組合せの個数は、
通りだからです。
からに落ちるのは地味に嬉しい。
このテクニックが有効な問題例:
直感的理解
(T-1)&S
は「T
の次に辞書順で小さい集合とS
の共通部分」である。これは「S
の部分集合全体の上でT
の次に辞書順で小さい集合」をとる操作になっているため、「T
より辞書順で小さいS
の部分集合のうち辞書順最大の集合」となる。
よって降順ですべての部分集合が生成され、最終的に0b0
になってループが終了する。
数学的理解
定義1
とおき、を適当な正の整数とする。
上の二項関係を、に対し辞書式順序: \begin{align} \mathbf{A} \leq \mathbf{B} :\iff \mathbf{A} = \mathbf{B} \lor \left(a_j < b_j \,\mathrm{ where }\, j=\min\{i\in\{1, \cdots, n\} \mid a_i \neq b_i \} \right) \end{align} で定めたとき全順序集合が与えられる。有限集合かつ全順序集合なので演算、が自然に定まる。最小元をとおく。
上の二項関係を、に対し
\begin{align} \mathbf{A} \subset \mathbf{B} :\iff ^\forall i\in\{1, \cdots, n\}, a_i\leq b_i \end{align}
で定義する。これはとを集合としてみたときの部分集合の関係に相当する。よって便宜上、が成り立つとき「はの部分集合」ということとする。
上の二項演算を、に対し \begin{align} \mathbf{A} \cap \mathbf{B} := (\min\{s_i, t_i\})_{i=1}^n \end{align} で定義する。これはとを集合としてみたときの共通部分に相当する。
写像をに対して \begin{align} \mathrm{dec}(\mathbf{A}) := \max\{\mathbf{B} \in \mathbf{2}^n \mid \mathbf{B} < \mathbf{A}\} \end{align} で定義する。は、辞書式順序での次に小さいものを表す。
対応付け
以上の定義から、bitによる集合表現と演算は次のように対応付けられる。
uint S
による集合:uint T
はuint S
の部分集合:S & T
の演算結果:S - 1
の演算結果:- ここで、この演算はに対しては定義されていないことに注意
定義2
集合を固定する。
上の列: \begin{align} &\mathbf{S}=\mathbf{S}_1 > \mathbf{S}_2 > \cdots > \mathbf{S}_k = \mathbf{O} \\ &\mathrm{ where }\, \{\mathbf{S}_1, \mathbf{S}_2, \cdots, \mathbf{S}_k\} = \{\mathbf{A}\in\mathbf{2}^n \mid \mathbf{A}\subset\mathbf{S}\} \end{align} とする。つまり、列は、の部分集合全体を降順に並べた列である。
とに対して、定義よりとなるような部分集合は存在しないので \begin{align} \mathbf{S}_{i+1} = \max\left\{\mathbf{A}\subset\mathbf{S}\mid \mathbf{A}<\mathbf{S}_i\right\} \end{align} が成り立つ。
さらに上の列を次のように帰納的に定める:
- ならば
- ならば
列は、上のbitテクニックによって生成されるuint T
の値の列に対応する。
命題
次が成り立つ。 \begin{align} (\mathbf{S}_i)_{i=1}^k = (\mathbf{T}_i)_{i=1}^k \end{align} これは、上のbitテクニックによる部分集合の列挙が正しいことを表している。
証明
は明らかに成り立つので、 が成り立つことを示せば帰納法より十分。
が成り立つと仮定すると
\begin{align} \mathbf{T}_{i+1} &= \mathrm{dec}(\mathbf{T}_i) \cap \mathbf{S}& \because \mathbf{T}_{i+1} \text{の定義}\\ &= \max\left\{\mathbf{A}\in\mathbf{2}^n\mid \mathbf{A}\subset\left(\mathrm{dec}(\mathbf{T}_i)\cap \mathbf{S}\right)\right\}& \because \mathbf{X}\subset\mathbf{Y} \Rightarrow \mathbf{X} \leq \mathbf{Y}\\ &= \max\left\{\mathbf{A}\in\mathbf{2}^n\mid \mathbf{A}\subset\left( \max\{\mathbf{B}\in\mathbf{2}^n \mid \mathbf{B}<\mathbf{T}_i\} \cap \mathbf{S}\right)\right\}& \because \mathrm{dec} \text{の定義}\\ &= \max\left\{\mathbf{A}\in\mathbf{2}^n\mid \mathbf{A}\subset \max\{\mathbf{B}\subset\mathbf{S} \mid \mathbf{B}<\mathbf{T}_i\}\right\}& \because \mathbf{B}<\mathbf{T}_i \Rightarrow \mathbf{B}\cap\mathbf{S}<\mathbf{T}_i\\ &= \max\left\{\mathbf{A}\in\mathbf{2}^n\mid \mathbf{A}<\mathbf{T}_i \land \mathbf{A}\subset\mathbf{S}\right\}\\ &= \max\left\{\mathbf{A}\subset\mathbf{S}\mid \mathbf{A}<\mathbf{T}_i \right\}\\ &= \max\left\{\mathbf{A}\subset\mathbf{S}\mid \mathbf{A}<\mathbf{S}_i \right\}& \because \mathbf{T}_i = \mathbf{S}_i\\ &= \mathbf{S}_{i+1}& \because \mathbf{S}_{i+1} \text{の性質} \end{align}
が成り立つ。
以上より、が成り立つ。
感想とか
- bitによる集合の表現は、集合上の部分集合を表すもの
- はと同一視できる
- のブール代数における演算はbit演算と対応する
大事な部分を抽出するとこんな感じでしょうか。
「代数の概念を用いて対象を同一視して捉えると、ものごとがすんなり理解できる」というのが最近の思うところです。同一視さいこう。
余談ですが、bitテクニックは調べるとおもしろいものがたくさんあってたのしいです。これとか、初めて見たときは感動しました。