読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

マジ数学本に敢てプログラムで挑戦(1):包除原理(Inclusion-Exclusion Principle)

SpringerのGTMと言えば黄色のカバーで有名ですが、238 A Course in Enumerationに包除原理を使った面白い問題が

Ex. 5.7.

How many integer solutions \( x_1+x_2+x_3+x_4=30 \) exist with the restriction -10 \le x_{i} \le 20 ?

上限が無ければよくある問題でcombinationで計算できます。

O(n4)

数字が小さいので四重ループで解けます、がO(n4)なのでNが大きいとお手上げです。

N=30
L=-10
R=20

def f_bf
    ret=0
    L.upto(R){|x|
        L.upto(R){|y|
            L.upto(R){|z|
                L.upto(R){|w|
                    ret+=1 if x+y+z+w==N
        }}}}
    ret
end

O(n2)

次に考えるのは4変数一括ではなく2変数ずつで考える。具体的には\( x_1+x_2 \) の取りうる組み合わせ計算しておき、 x_1+x_2=a となる個数と x_3+x_4=30-a を満たす個数をかけ合わせて行く方法。これはO(n2)で計算できる。

def f_dc
    memo=Array.new((R-L)*2+N,0)
    L.upto(R){|x|
        (x+1).upto(R){|y|
            memo[x+y]+=2
    }}
    L.upto(R){|x|memo[2*x]+=1}
    ret=0
    (2*L).upto(2*R){|i|
        ret+=memo[i]*memo[N-i]
    }
    ret
end

O(1)

最後の方法が包除原理を使ったもので、これが一番早い。まず初めに、次の事実に注意:

\( x_1+x_2+x_3+x_4=30 \)を満たす正整数の組み合わせ個数は  _{29} C_3 である

これは、ボールを30個横に並べて3つの衝立で分割すること(◯◯|◯・・◯◯|◯・・◯|◯◯◯)に方程式の解が一対一に対応し、衝立を入れる場合の数は29箇所から3つ選ぶことになるから。次に\( y_i=x_i+10 \) と変形することで同値な問題

How many integer solutions \( (\ast) \ y_1+y_2+y_3+y_4=70 \) exist with the restriction (\star) \ 0 \le y_{i} \le 30 ?

にできます。すると求めるのは包除原理より、

(\ast) を満たす正整数の組み合わせ数-(\ast) を満たすけど1変数だけ(\star)を満たさない+(\ast) を満たすけど2変数だけ(\star)満たさない・・・

となりますね。j個の変数だけ(\star)を満たさないということはj個の変数の値は31以上。つまりj個の変数を\( z_i=y_i-31 \) とすることで元と同じ問題、ただし総和が70-31*jを解くことに帰着されます。4変数のうちj個を選ぶのは _4 C_j ですから結局次のようなアルゴリズムになります。

def f_inc_exc
    n=4
    k=N-L*n
    s=R-L+1
    #new problem: find the # of sol x+y+z+w=70 with the restriction 0<= each<=30?
    ret=0
    0.upto(n){|j|
        sgn=j.odd? ? -1 : 1
        temp=sgn*combination(n,j)*combination(n+k-j*s-1,n-1)
        ret+=temp
    }
    ret
end

小さいNでは差が分かりませんが大きいと違いは明らか。ブルートフォース版は10分待っても帰ってきませんでした。

N=10000
L=-5000
R=7000

       user     system      total        real
inclusion & exclusion : 828252025001
  0.000000   0.000000   0.000000 (  0.000093)
divide & conquer      : 828252025001
  7.710000   0.020000   7.730000 (  7.735661)
bruteforce            : ^Cex05_07.rb:12:in `block (4 levels) in f_bf': Interrupt

A Course in Enumeration (Graduate Texts in Mathematics)

A Course in Enumeration (Graduate Texts in Mathematics)