積集合の抽出に挑む 3 戦略

この問題は、「モノの集合→モノを全て含む集合の列挙」として解くこともできるし、「集合を列挙する→それらが共有するモノの集合」とみて解くこともできる。というのは、「集合はどのモノを含むか」と「モノはどの集合に含まれるか」がよい対称を為しているからである。そのままモノ∈集合としてもいいし、集合∈モノとして考えても良いのである。

しかしながらここでは、集合が200くらいなのに対してモノが100種類くらいのケースを考える。一般的に列挙というものは小さいループで回した方がいい。つまり「集合を列挙する→それらが共有するモノの集合」という方向ではなく、「モノの集合→モノを全て含む集合の列挙」という方向で解く方がいいことが多い。それでもループは下手したら2^100のオーダーになる。

そこで、積極的に枝刈りを行う。実際にモノを幾つか選んでいくと、もう選べないモノが出てくる。A={a,b,c} B={a,b,d} C={c,d,e}で考える。モノは全て合わせると{a,b,c,d,e}となるが、aを選んだ時点でもうc,d,eは選べない。もしcを選んでしまうと{a,c}∈Aだけになってしまうからである。この枝刈りは、集合やモノが増えるとものすごく効いてくる。

実際の枝刈りはどうするか。「モノ」→「モノを含む集合」を求めておくのである。例えばa→{A,B} b→{A,B} c→{A,C} d→{B,C} e→{C}とする。そうすれば{a,b}→{A,B} {a,c}→{A}ということもすぐにわかる。

さてこれをどう実現するか。ひとつはハッシュ→配列としてもっておき、モノを複数選んだら、モノをすべて含む集合たちを、配列の共通部分として取り出す方法がある。もうひとつは、ハッシュ→ビット列としてもっておき、モノを複数選んだら、モノをすべて含む集合たちを、ビット列のand演算結果として取り出す方法である。

前者は配列の共通部分を計算するのに時間がかかり、後者はビット列から集合の列挙に戻すのに時間がかかる。ここでは後者でスクリプトを組むことにする。