DouKaku? 4546 [1..100]>>=pen: 今度は大丈夫かな。現在手元にまともな...(自然数の分割（別表現）)

Comment detail

今度は大丈夫かな。
現在手元にまともなマシンがないので実行時間は後日。

import List

main = putStr $ unlines $ map (unlines . map (bou!!))
  $ partitions 50 where
  bou = iterate ("[]"++) ""

partitions n = [1..n] >>= partitions' n  where
  partitions' n m = map (map sum.transpose.(:[ones]))
    $ f (n-m) m (n-m)  where ones = replicate m 1
  f _ 0 _ = [[]]
  f n m p = [x:xs| let p' = min n p, x <- [p',p'-1..(n+m-1)`div`m], xs <- f (n-x) (m-1) x]

ミスがあった。orz

1 2	-- f _ 0 _ = [[]] ++ f 0 _ _ = [[]]

前回のコードをもう少しすっきりさせました。

Windows XP
システムのプロパティ
  Pentium(R) 4 CPU 2.40GHz
  2.41 GHz, 0.99 GB RAM
ghc -O3 (GHC6.8.1)
ファイルにリダイレクトで５秒くらい。

main = putStr $ unlines $ map (unlines . map (bou!!))
  $ partitions 50 where
  bou = iterate ("[]"++) ""

partitions n = [1..n] >>= f n n  where
  f 0 _ m = return $ replicate m 1
  f n p m = [x:xs| let p' = min (n-m+1) p, x <- [p',p'-1..(n+m-1)`div`m], xs <- f (n-x) x (m-1)]

また間違えた。orz orz
（正しい答えを出してたけど意図したコードではなかった）
今度こそ。

Windows XP
システムのプロパティ
  Pentium(R) 4 CPU 2.40GHz
  2.41 GHz, 0.99 GB RAM
ghc -O3 (GHC6.8.1)
ファイルにリダイレクトで５秒くらい。

main = putStr $ unlines $ map (unlines . map (bou!!))
  $ partitions 50 where
  bou = iterate ("[]"++) ""

partitions n = [1..n] >>= f n n  where
  f n p m
    | n <= m    = [replicate m 1]
    | otherwise = [x:xs| let p' = min (n-m+1) p, x <- [p',p'-1..(n+m-1)`div`m], xs <- f (n-x) x (m-1)]

すばらしいですねー。
私の脳みそでは理解するのにすら数時間かかりました(^_^;

#4546では、f (n-m) m (n-m) で箱の数(n-m)、行数m以下、列数(n-m)以下のヤング図形を全て作って、最後に左に高さmの列を付け加えるわけですね。
一方#4586の f n p m では、直接行数がちょうどmのヤング図形を生成すると。

(n+m-1) `div` m とかにも熟練を感じます。
勉強になりました。

ところで7行目の <= は、 < の場合も拾うのは気持ちが悪いので、== でいいのではないでしょうか。
なんか重箱の隅をつつくようで申し訳ないですが。

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq