魔方分割数 in Clean DouKaku?

1 .. N^2までの数をN個の数字の和が等しいN個のグループに分けたいと思います。

たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。

ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。

なお、数え上げるときの注意として、

・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの

・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
　{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。

とりあえずナイーブに実装。

n=4の場合、0.04秒ですが、n=5の場合、5分経っても終わらないです。

see: AltEnvライブラリを使っています

module Main

import Bool, Int, List, Array, ValueCast, StringCast, System, Misc

Start = length $ divide n s ls
  where
  n = toInt getCommandLine.[1]
  ls = [1..n*n]
  s = sum ls / n

divide n s ls = search ls
  where
  search [] = [[]]
  search ls
    =  comb n ls
    |> filter (\f = sum f == s)
    |> map (\f = let
                   (f0,fr) = (head f, tail f)
                   rr = filter (\e = not (e <= f0 || fr contains e)) ls
                 in [[f:t] \\ t <- search rr])
    |> foldr (++) []

comb :: Int [a] -> [[a]]
comb 0 _ = [[]]
comb _ [] = []
comb n [e:rr]
  =  map ((:>) e) (comb (n-1) rr)
  ++ comb n rr

いくつか高速化を試して、一番効果の高かったcomb_sumでの置き換えだけを適用したもの。

n=5で、2分20秒

効果があまりなかったものは、コメントに記述してあります。

see: AltEnvライブラリを使っています

module Main

import Bool, Int, List, Array, ValueCast, StringCast, System, Misc

Start = length $
        divide n s ls
  where
  n = toInt getCommandLine.[1]
  ls = [1..n*n]
  s = sum ls / n

divide n s ls = search ls
  where
  search [] = [[]]
  search ls
    =  comb_sum s n ls
    |> map (\f = let
                   (f0,fr) = (head f, tail f)
                   rr = filter (\e = not (e <= f0 || fr contains e)) ls
                 in [[f:t] \\ t <- search rr])
    |> foldr (++) []

comb_sum :: Int Int [Int] -> [[Int]]
comb_sum 0 0 _ = [[]]
comb_sum _ 0 _ = []
comb_sum s _ [] = []
comb_sum s n [e:rr]
  | e > s
    = comb_sum s n rr
    = map ((:>) e) (comb_sum (s-e) (n-1) rr) ++ comb_sum s n rr

/*
  //1. filterの部分をrest_of関数で置き換え
  search [] = [[]]
  search ls
    =  comb_sum s n ls
    |> map (\f = let rr = rest_of f ls
                 in [[f:t] \\ t <- search rr])
    |> foldr (++) []

  rest_of _ [] = []
  rest_of es=:[e:ee] ls=:[l:ll]
    | l <= e = rest_of es ll
    = rm ee ls
    where
    rm _ [] = []
    rm [] ls = ls
    rm es=:[e:ee] ls=:[l:ll]
      | l < e  = [l: rm es ll]
      | e == l = rm es ll
               = rm ee ls

  //2. searchで直接グループわけの個数を計算
  search [] = 1
  search ls
    =  comb_sum s n ls
    |> map (\f = let rr = rest_of f ls
                 in search rr)
    |> sum
*/

comb_sumで明らかに無駄な数え上げをしているところがあったので、それを削除しました

n=5で18秒まで減少しました

see: AltEnvライブラリを使っています

module Main

import Bool, Int, List, Array, ValueCast, StringCast, System, Misc, Trace

Start = length $
        divide n s ls
  where
  n = toInt getCommandLine.[1]
  ls = [1..n*n]
  s = sum ls / n

divide n s ls = search ls
  where
  search [] = [[]]
  search ls
    =  comb_sum s n ls
    |> map (\f = let
                   (f0,fr) = (head f, tail f)
                   rr = filter (\e = not (e <= f0 || fr contains e)) ls
                 in [[f:t] \\ t <- search rr])
    |> foldr (++) []

comb_sum :: Int Int [Int] -> [[Int]]
comb_sum s n [e:ee]
  | e > s = []
  = map ((:>) e) (comb_sum (s - e) ck ee) // <- この部分を修正
  where
  ck = reverse $ take (n-1) $ scan (+) 0 $ reverse $ ee
  comb_sum 0 [] _ = [[]]
  comb_sum _ [] _ = []
  comb_sum _ _ [] = []
  comb_sum s ck=:[c:cc] [e:ee]
    | e > s     = []
    | e < s - c = comb_sum s ck ee
                = map ((:>) e) (comb_sum (s-e) cc ee) ++ comb_sum s ck ee

DouKaku?

魔方分割数

Posted feedbacks - Clean

Index

Feed

Other

Link

Pathtraq