Project Euler 106（2）

http://projecteuler.net/index.php?section=problems&id=106

前回は集合のペアを生成してチェックしなければならないかどうか判定しましたが、チェックしなければならない集合のペアを直接生成できないでしょうか。これは難しそうですが、逆にチェックしなくてもいい集合のペアは簡単に生成できます。実際には数を数えればいいだけなので生成はせずに個数を返す関数を作ります。

def F(n):
    def count_pairs(n, diff):
        if diff == 0:
            return count_pairs(n - 1, diff + 1)
        elif diff == n:
            return 1
        else:
            return count_pairs(n - 1, diff + 1) \
                 + count_pairs(n - 1, diff - 1)
    
    return count_pairs(n - 1, 1)

F(n)はBとCであわせてn個の要素でチェックしなくてもいいペアの個数です。
n個の要素を並べて、小さいほうから順にBとCに振り分けていきます。このとき、常にBの要素数がCのそれより大きいかまたは等しくなければなりません。上のdiffはその差です。
さらに、メモ化すると非常に速くなります。ただし、Aの要素数が1000だと再帰が深くなりすぎるので、sys.setrecursionlimitで上限を変えます。これで、2秒程度になりました。

import sys

def C(n, m):
    return 1 if m == 0 else C(n, m - 1) * (n - m + 1) / m

def F(n):
    def count_pairs(n, diff):
        x = (n, diff)
        if x in memo:
            return memo[x]
        
        if diff == 0:
            v = count_pairs(n - 1, diff + 1)
        elif diff == n:
            v = 1
        else:
            v = count_pairs(n - 1, diff + 1) \
              + count_pairs(n - 1, diff - 1)
        
        memo[x] = v
        return v
    
    return count_pairs(n - 1, 1)

def count_pair_of_sets(n):
    return sum(C(n, m) * (C(m, m / 2) / 2 - F(m))
                            for m in range(2, n + 1, 2))

sys.setrecursionlimit(2000)
N = 1000
memo = { }
print count_pair_of_sets(N)