Project Euler 106

プロジェクトオイラー
http://projecteuler.net/index.php

Q106.
（省略）

まず、同じ大きさの部分集合の対のみ考えればよい。n = 7として、集合の要素に番号0〜6を付け、部分集合を次のように表す：{ 0, 2, 4 }, { 1, 3, 5 }。このようにソートしておき、対になる要素の大小が一定ならtest1は行う必要がない。重複に注意。

from itertools import *
def test(A, B):

    return test1(A, B) and test2(A, B)
def test1(A, B):

    for p, q in zip(A, B):

        if p > q:

            return True

    return False
def test2(A, B):

    for p, q in zip(A, B):

        if p < q:

            return True

    return False
# m x m

def num_test_core(n, m):

    counter = 0

    for A in combinations(range(n), m):

        res = [ 0 ] * (n - m)

        k = 0

        l = 0

        for i in range(n):

            if k < m and A[k] == i:

                k += 1

            else:

                res[l] = i

                l += 1

        for B in combinations(res, m):

            if test(A, B):

                counter += 1

    return counter / 2
def num_test(n):

    return sum(map(lambda m: num_test_core(n, m), range(2, n / 2 + 1)))
n = 12

print num_test(n)