ビット列で集合を表現する方法は、集合の演算を高速に行うためによく使われている方法です。 ですが、冪集合をビット列で表す方法はあまり使われていないかもしれません。普通の集合演算に加えて、面白くて効率の良いアルゴリズムを考えたので、紹介いたします。
集合をビット列で表す
集合$A$の要素一つ一つにビットを割り当てます(例：$a$が1ビット目、$b$が2ビット目、$c$が3ビット目)。そして、その集合を要素を含むときにそのビットが1になるビット列で表します。例えば：
\begin{align}
\phi &= (000) \\
\{a, b\} &= (110) \\
\{a, b, c\} &= (111)
\end{align}
すると、多くの集合演算はビット演算に対応できます。(以下$A=\{a, b\} = (110)$、$B=\{c\} = (001)$とする)
| 演算 | 集合演算 | ビット演算 |
|---|---|---|
| 積集合 | $A\cap B$ | (110) & (001) = (000) |
| 和集合 | $A\cup B$ | (110) ｜ (001) = (111) |
| 補集合 | $\overline{A}$ | ~(110) = (001) |
| 部分集合判定 | $A\subseteq B$ | (110) & (001) === (001) |
冪集合とは?
ある集合$A=\{a, b, c\}$を考えます。するとその冪集合$2^A$は$A$の部分集合の集合となります。つまり、
\begin{align}
2^A &= \{\phi, \{a\},\{b\},\{c\},\{a, b\},\{a, c\},\{b, c\}, \{a, b, c\}\}
\end{align}
冪集合の部分集合をビット列で表す
本題です。ビット列で表された集合を整数に直します(例:(110) = 6)。そして、冪集合の部分集合がその集合を含む時、その整数番目のビットが1となるビット列で表します。例えば：
\begin{align}
\{\phi, \{a, b\}, \{a, b, c\}\} = (10100001)
\end{align}
冪集合も集合なので、上記に示した演算が使えます。
メリット&デメリット
メリット
- メモリが節約できる
- 演算が早い。（和集合演算ならば$n$を元の集合の要素数とすると、$O(2^n)$から$O(1)$になる)
デメリット
- 冪集合の部分集合の要素数が通常少ない場合、要素のリストを作成した方がメモリ効率が良い時がある。
- $n$が大きくなると使えなくなる(32bitの場合$n\leq 5$まで。Javaの
BigIntegerとかGPUとか使えばもっとできるかもしれないけど)
ある集合の部分集合となる集合の集合を得る
...ていうと訳わからんので、次の演算subsetを考えます
\mathop{subset}(B) = \{A'\in 2^A\mid A'\subseteq B\}
簡単に考えれば次のような演算で計算できます
function subset(b: number, n: number) {
let result = 0;
for(let i = 0; i < 1 << n; i++) {
if(b & i === i) result += 1 << i;
}
}
$O(2^n)$ですね。こんなの遅くて使えませんね(笑)
次でできます
export function subset(b: number): number {
let val = 1;
let cnt = 0;
let tmp = b;
while(tmp !== 0) {
if((tmp & 1) === 1) {
val += val << (2 ** cnt);
}
tmp >>>= 1;
cnt ++;
}
return val & ((1 << (b + 1)) - 1);
}
$O(n)$ですね。どうしてこれでできるのか?説明するのが面倒なので興味がある人は考えてみてください。
派生
\mathop{subsetStrict}(B) = \{A'\in 2^A\mid A'\subset B\}
export function subsetStrict(b: number): number {
let val = 1;
let cnt = 0;
let tmp = b;
while(tmp !== 0) {
if((tmp & 1) === 1) {
val += val << (2 ** cnt);
}
tmp >>>= 1;
cnt ++;
}
return val & ((1 << b) - 1);
}
\mathop{superset}(B) = \{A'\in 2^A\mid B\subseteq A'\}
export function superset(b: number, n: number): number {
return subset(~b & ((1 << n) - 1));
}
\mathop{supersetStrict}(B) = \{A'\in 2^A\mid B\subset A'\}
export function supersetStrict(b: number, n: number): number {
return subsetStrict(~b & ((1 << n) - 1))
}
まとめ
使う機会はほとんど無いとは思いますが、誰かの役に立てたら幸いです。面白くて高速な集合演算を知っている・思いついた方がいたら教えてください！