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;
        // 処理
    }
}

これだと全体の計算量は $O(2^n \cdot 2^n) = O(4^n)$ になりますが、上述のbitテクニックを使うと

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

となり $O(3^n)$ になります。なぜなら、SとTの組合せの個数は、 $\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)$に落ちるのは地味に嬉しい。

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

• ARC056 C - 部門分け

直感的理解

(T-1)&Sは「Tの次に辞書順で小さい集合とSの共通部分」である。これは「Sの部分集合全体の上でTの次に辞書順で小さい集合」をとる操作になっているため、「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$に対し辞書式順序:

$$\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}$$ で定めたとき全順序集合$(\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$に対し

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

で定義する。これは$\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$に対し

$$\begin{align} \mathbf{A} \cap \mathbf{B} := (\min\{s_i, t_i\})_{i=1}^n \end{align}$$ で定義する。これは$\mathbf{A}$と$\mathbf{B}$を集合としてみたときの共通部分に相当する。

写像$\mathrm{dec}\colon \mathbf{2}^n-\{\mathbf{O}\} \to \mathbf{2}^n$を$\mathbf{A}\in \mathbf{2}^n-\{\mathbf{O}\}$に対して

$$\begin{align} \mathrm{dec}(\mathbf{A}) := \max\{\mathbf{B} \in \mathbf{2}^n \mid \mathbf{B} < \mathbf{A}\} \end{align}$$ で定義する。$\mathrm{dec}(\mathbf{A})$は、辞書式順序で$\mathbf{A}$の次に小さいものを表す。

対応付け

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

• uint Sによる集合: $\mathbf{S} = (s_i)_{i=1}^n \in \mathbf{2}^n$
• uint Tはuint 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$上の列:

$$\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}$$ とする。つまり、列$(\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}$は存在しないので

$$\begin{align} \mathbf{S}_{i+1} = \max\left\{\mathbf{A}\subset\mathbf{S}\mid \mathbf{A}<\mathbf{S}_i\right\} \end{align}$$ が成り立つ。

さらに$\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の値の列に対応する。

命題

次が成り立つ。

$$\begin{align} (\mathbf{S}_i)_{i=1}^k = (\mathbf{T}_i)_{i=1}^k \end{align}$$ これは、上の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{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}$$

が成り立つ。

以上より、$(\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テクニックは調べるとおもしろいものがたくさんあってたのしいです。これとか、初めて見たときは感動しました。

参考文献

• bit演算による集合の列挙 | うさぎ小屋
• ビットによる部分集合の列挙 | SRM diary(Sigmar)
• プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～