Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

bitによる部分集合の列挙 と 数学的理解

bitテクニックで、集合の部分集合を列挙するものがあります。その紹介と数学的理解です。

bitによる部分集合の列挙

集合uint Sに対して、Sの部分集合Tは次のようにして全列挙できます。

uint S; // <- 集合
for (uint T=S; ; T=(T-1)&S) {
    // 処理
    if (T==0) break;
}

例えばS0b100101のときは、Tforの中で、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;
        // 処理
    }
}

これだと全体の計算量はO(2^n \cdot 2^n) = O(4^n)になりますが、上述のbitテクニックを使うとO(3^n)になります。なぜなら、STの組み合わせの総数は、 \displaystyle \sum_{S=0}^{2^n-1} 2^{\mathrm{popcount}(S)} = \sum_{i=0}^n {}_n C_i 2^i = (2 + 1)^n = 3^n通りだからです。

O(4^n)からO(3^n)に落ちるのは地味に嬉しい。

このテクニックが有効な問題例:

直感的理解

(T-1)&Sは、「Tの最大の真部分集合」かつ「Sの部分集合」なので、「Tより真に小さい最大のSの部分集合」となる。

よって降順ですべての部分集合が生成され、最終的に0b0になってループが終了する。

数学的理解

定義1

\mathbf{2} := \{0, 1\}とおき、nを適当な正の整数とする。

\mathbf{2}^n上の二項関係\leqを、\mathbf{A} = \mathbb(a_i)_{i=1}^n, \mathbf{B}=(b_i)_{i=1}^n \in \mathbf{2}^nに対し辞書式順序:

$$\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)$$

で定めたとき全順序集合(\mathbf{2}^n, \leq)が与えられる。有限集合かつ全順序集合なので演算\min\maxが自然に定まる。最小元を\mathbf{O}:=\min (\mathbf{2}^n) = (0)_{i=1}^nとおく。

\mathbf{2}^n上の二項関係\subsetを、\mathbf{A} = \mathbb(a_i)_{i=1}^n, \mathbf{B}=(b_i)_{i=1}^n \in \mathbf{2}^nに対し

$$\mathbf{A} \subset \mathbf{B} :\iff ^\forall i\in\{1, \cdots, n\}, a_i\leq b_i$$

で定義する。これは\mathbf{A}\mathbf{B}を集合としてみたときの部分集合に相当する。よって便宜上、\mathbf{A} \subset \mathbf{B}が成り立つとき「\mathbf{A}\mathbf{B}の部分集合」ということとする。

\mathbf{2}^n上の二項演算\capを、\mathbf{A} = \mathbb(a_i)_{i=1}^n, \mathbf{B}=(b_i)_{i=1}^n \in \mathbf{2}^nに対し

$$\mathbf{A} \cap \mathbf{B} := (\min\{s_i, t_i\})_{i=1}^n$$

で定義する。これは\mathbf{A}\mathbf{B}を集合としてみたときの共通部分に相当する。

写像\mathrm{dec}\colon \mathbf{2}^n-\{\mathbf{O}\} \to \mathbf{2}^n\mathbf{A}\in \mathbf{2}^n-\{\mathbf{O}\}に対して $$\mathrm{dec}(\mathbf{A}) := \max\{\mathbf{B} \in \mathbf{2}^n \mid \mathbf{B} < \mathbf{A}\}$$ で定義する。\mathrm{dec}(\mathbf{A})は、辞書式順序で\mathbf{A}の次に小さいものを表す。

対応付け

以上の定義から、bitによる集合表現と演算は次のように対応付けられる。

  • uint Sによる集合: \mathbf{S} = (s_i)_{i=1}^n \in \mathbf{2}^n
  • uint Tuint Sの部分集合: \mathbf{T}\subset \mathbf{S}
  • S & Tの演算結果: \mathbf{S} \cap \mathbf{T} \in \mathbf{2}^n
  • S - 1の演算結果: \mathrm{dec}(\mathbf{S}) \in \mathbf{2}^n
    • ここで、この演算は\mathbf{O}\in\mathbf{2}^nに対しては定義されていないことに注意

定義2

集合\mathbf{S}\in \mathbf{2}^nを固定する。

\mathbf{2}^n上の列: $$\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}\}$$ とする。つまり、列(\mathbf{S}_i)_{i=1}^kは、\mathbf{S}の部分集合全体を降順に並べた列である。

\mathbf{S}_i\mathbf{S}_{i+1}に対して、定義より\mathbf{S}_i>\mathbf{A}>\mathbf{S}_{i+1}となるような部分集合\mathbf{A}\subset\mathbf{S}は存在しないので$$\mathbf{S}_{i+1} = \max\left\{\mathbf{A}\subset\mathbf{S}\mid \mathbf{A}<\mathbf{S}_i\right\}$$が成り立つ。

さらに\mathbf{2}^n上の列(\mathbf{T}_i)_{i=1}^\inftyを次のように帰納的に定める:

  • \mathbf{T}_1 := \mathbf{S}
  • \mathbf{T}_i \neq \mathbf{O}ならば\mathbf{T}_{i+1} := \mathrm{dec}(\mathbf{T}_i) \cap \mathbf{S}
  • \mathbf{T}_i = \mathbf{O}ならば\mathbf{T}_{i+1} := \mathbf{O}

(\mathbf{T}_i)_{i=1}^\inftyは、上のbitテクニックによって生成されるuint Tの値の列に対応する。

命題

次が成り立つ。

$$(\mathbf{S}_i)_{i=1}^k = (\mathbf{T}_i)_{i=1}^k$$

これは、上のbitテクニックによる部分集合の列挙が正しいことを表している。

証明

\mathbf{S}_1=\mathbf{T}_1=\mathbf{S}が明らかに成り立つので、\mathbf{S}_i=\mathbf{T}_i\neq \mathbf{O} \Rightarrow \mathbf{S}_{i+1}=\mathbf{T}_{i+1}が成り立つことを示せば帰納法より十分。

\mathbf{S}_i=\mathbf{T}_i \neq \mathbf{O}が成り立つと仮定すると

\begin{aligned}
\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 \cap \text{の定義}\\
&= \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\}\\
&= \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{aligned}

が成り立つ。

以上より、(\mathbf{S}_i)_{i=1}^k = (\mathbf{T}_i)_{i=1}^kが成り立つ。

感想とか

  • bitによる集合の表現は、集合\{1, \cdots, n\}上の部分集合を表すもの
  • 2^{\{1, \cdots, n\}}\mathbf{2}^nと同一視できる
  • \mathbf{2}ブール代数における演算はbit演算と対応する

大事な部分を抽出するとこんな感じでしょうか。

「代数の概念を用いて対象を同一視して捉えると、ものごとがすんなり理解できる」というのが最近の思うところです。同一視さいこう。

余談ですが、bitテクニックは調べるとおもしろいものがたくさんあってたのしいです。これとか、初めて見たときは感動しました。

参考文献