DouKaku? 4915 [1..100]>>=pen: comb の方にも和の制約を入れたら手元...(魔方分割数)

Comment detail

This comment is reply for 4878 nobsun: 条件を満す組み合せを生成するが、できるだ...(魔方分割数). Go to thread root.

comb の方にも和の制約を入れたら手元のマシンで
magic 5 のケースが４倍速になりました。

comb :: Int -> Int -> [Int] -> [([Int],[Int])]
comb s _ xs | s < 0 = []
comb s 0 xs | s == 0    = [([],xs)]
            | otherwise = []
comb _ _ [] = []
comb s k (x:xs) = [ (x:ys,zs) | (ys,zs) <- comb (s-x) (k-1) xs ]
                ++[ (ys,x:zs) | (ys,zs) <- comb s     k     xs ]

comb' :: Int -> Int -> [Int] -> [([Int],[Int])]
comb' s 0 xs | s == 0    = [([],xs)]
             | otherwise = []
comb' _ _ []             = []
comb' s k (x:xs) = [ (x:ys,zs) | (ys,zs) <- comb (s-x) (k-1) xs ]

もう少し速くなりました。
ついでにグループ分けの数を求めるのに必要な部分だけに削りました。

module Main (main) where

import Data.List
import System.Environment

comb s 0 xs | s == 0    = [xs]
            | otherwise = []
comb s k (x:xs)
  | k * x > s = []
  | otherwise = comb (s-x) (k-1) xs ++ map (x:) (comb s k xs)
comb _ _ _ = []

comb' s k (x:xs)
  | k * x > s = []
  | otherwise = comb (s-x) (k-1) xs
comb' _ _ _ = []

magic n = iterate (concatMap (comb' s n)) [ns] !! n
  where ns = [1..n^2]
        s  = sum ns `div` n

main = print . length . magic . read . head =<< getArgs

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq