Inclusion--Exclusion Algorithms for Counting Set Partitions (Part 1)

A. Björklund and T. Husfeldt. Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS 2006.

備忘録がてら記事を書いていたら長くなったのでとりあえずPart 1．

http://d.hatena.ne.jp/wata_orz/20120329
にて彩色数を $O(2^{n}n)$ で求めるアルゴリズムの論文があったので読んでみた．

やりたいこと

包除原理による集合分割の数え上げ

彩色グラフ
- 彩色数
- k-彩色の方法の総数
- 彩色多項式

支配数

以下，G=(V,E)，n=|V|とする．

問題を一般化して，頂点集合Vの冪集合の部分集合Pからk個の集合を選び，V全体を被覆or分割する方法の総数を求めることにする．彩色数ならば，独立集合によるVの被覆を，支配数ならば，支配集合によるVの分割を考える．

包除原理

集合に関する関数 $g(S)$ があった時，
$f(S)=\sum_{T \subseteq S}g(T)$
$g(S)=\sum_{T \subseteq S}(-1)^{|S|-|T|}f(T)$

k-被覆の個数

Pからk個の集合を選んでVを被覆する方法の総数を求める．

$g(S)$ ：Pから選んだk個の集合がSを丁度覆う方法の総数
とすると，求めるべきものは $g(V)$ である．
$f(S)=\sum_{T \subseteq S}g(T)$
は，「Pから選んだk個の集合がSの部分集合のみを覆う方法の総数」になるので，
$f(S)$ ：Sの部分集合をPからk個選ぶ方法の総数
となる．従って，
$I(S)$ ：Sの部分集合でPに含まれるものの個数
とすると， $f(S)=I(S)^{k}$ ．
ある集合 $S$ が $S \in P$ かを判定出来るならば， $I(S)$ は簡単に計算できる．

$I(S)$ の一般的な求め方

あるSがPに属すかを簡単に判定出来るとし，以下を定義する．
$a(S)=[S \in P$ ]
つまり $a(S)$ は，SがPに入っている時1，そうでない時は0．この時，全てのSについて，
$I(S)=\sum_{T \subseteq S}a(T)$
を求めればよいが，これは高速ゼータ変換を用いれば， $O(2^{n}n)$ で計算可能．

全体のコードはこんな感じ．

int[] I=new int[1<<n];
for(int s=0; s<1<<n; s++){
    // I[s]=sがPに入っているか
}

// 高速ゼータ変換 O(2^n*n)
for(int i=0; i<n; i++)
    for(int s=0; s<1<<n; s++)
        if((s>>i&1)==1)
            I[s]+=I[s^(1<<i)];

// 包除原理 O(2^n)
int g=0;
for(int i=0; i<1<<n; i++)
    if(bitCount(((1<<n)-1)^i)%2==0)
        g+=pow(I[i], k);
    else
        g-=pow(I[i], k);

明らかにgはオーバーフローするので，modをとるなどする必要がある（けど実はしなくても大丈夫）．

適用可能な問題

POJ 1620 Phone Home

k-分割の個数

Pからk個の集合を選んでVを分割する方法の総数を求める．

$g(S)$ ：Pから選んだk個の集合がSを丁度覆いかつサイズの和がnとなるような方法の総数
とすると，
$f(S)=\sum_{T \subseteq S}g(T)$
は，「Pから選んだk個の集合がSの部分集合のみを覆いかつサイズの和がnになるような方法の総数」になるので，
$f(S)$ ：サイズの和がnとなるSの部分集合k個をPから選ぶ方法の総数
となる．

$f(S)$ の一般化な求め方

高速ゼータ変換+DPで求められる．

$I(m,S)$ ：Sの部分集合でPに含まれかつサイズがmのものの個数
$dp(r,m,S)$ ：サイズの和がmとなるSの部分集合r個をPから選ぶ方法の総数
とし，まずI(m,S)を求め，以下の漸化式でdp(r,m,S)を求める．

$dp(1,m,S)=I(m,S)$
$dp(r,m,S) = \sum_{1 \leq i \leq m-1}I(m-i,S)dp(r-1,i,S)$

dp(k,n,S)は順列の個数を数えているので，
$f(S)=dp(k,n,S)/k!$
とかける．

コードは大体こんな感じ．

int[][] I=new int[n+1][1<<n];
for(int s=0; s<1<<n; s++){
    // I[m][s]=sがPに入っているかつsのサイズがmならば1
}

// 高速ゼータ変換 O(2^n*n^2)
for(int j=0; j<=n; j++)
    for(int i=0; i<n; i++)
        for(int s=0; s<1<<n; s++)
            if((s>>i&1)==1)
                I[j][s]+=I[j][s^(1<<i)];

// DP O(2^n*n^3)
int[][][] dp=new int[n+1][n+1][1<<n];
for(int s=0; s<1<<n; s++){
    for(int m=0; m<=n; m++)
        dp[1][m][s]=I[m][s];
    for(int r=2; r<=n; j++)
        for(int m=1; m<=n; m++)
            for(int i=1; i<=m-1; i++)
                dp[r][m][s]+=I[m-i][s]*dp[r-1][i][s];
}

// 包除原理 O(2^n)
int g=0;
for(int i=0; i<1<<n; i++)
    if(bitCount(((1<<n)-1)^i)%2==0)
        g+=dp(k,n,i)/factorial(k);
    else
        g-=dp(k,n,i)/factorial(k);

やはりこちらもdpの計算でオーバーフローするので注意（だけど実は対処しなくても大丈夫）．また，分割が存在するかどうかだけを調べたい場合は，k!で割る必要はない．DP部分が計算量 $O(2^{n}n^{3})$ で重い…．

適用可能な問題

SRM 388 Medium InformFriends