１０６問目

http://projecteuler.net/index.php?section=problems&id=106
１０３問目の関連問題。
大きさ n の集合 A の要素の和を S(A) とおく。空でなく共通の要素を持たない２つの部分集合 B, C が、以下の性質を持つような集合を特別な集合と呼ぶ。

1. S(B) ≠ S(C); つまり、部分集合の和は等しくない。
2. B が C より多くの要素を持つならば S(B) ＞ S(C)

集合 A が２つめの性質を既に満たしているとき、１つめの性質を満たすかどうかだけ調べればよい。
たとえば n = 4 のとき、25 組の考えられる部分集合の組のうち 1 組だけ調べれば十分である。また n = 7 のとき、966 組のうち 70 組を調べれば十分である。
n = 12 のとき、261625 組の部分集合の組に対して、１つめの性質を調べなくてはならないのは何組あるか求める。
２つめの性質が満たされているので、同じ要素数の部分集合を調べれば十分です。また、部分集合 B, C をそれぞれ昇順に並べて比較するとき、B の要素が常に C の要素より大きい／小さいのであれば、調べる必要はありません。
そういう部分集合の組がいくつあるか求めます。

import Data.List

main =  print $ euler106 12

euler106 :: Int -> Int
euler106 n = length $ concat [ pair [1..n] i | i <- [2..(div n 2)] ]

pair :: [Int] -> Int -> [([Int], [Int])]
pair xs n = [ (as, bs) |
    as <- comb xs n, bs <- comb (xs \\ as) n,
    as < bs, or $ zipWith (>) as bs ]
--  as < bs, any (\ (a, b) -> a > b) $ zip as bs ]

comb :: Ord a => [a] -> Int -> [[a]]
comb _ 0 = [[]]
comb xs m = [ x : xs' | x <- xs, xs' <- comb (filter (> x) xs) (m - 1) ]