Re: Graphical Partition

This entry was posted by on Friday, 7 October, 2005
>というわけで >この問題 >、問3をやってみた(そんなやつばっかしか)。 > >というか nobsun の解答はわからないので自分でやってみたというか。無駄に長いなあ。 > >perm :: [a] -> [[a]]
perm [] = []
perm l@(x:xs) = concat $ map perm_main
$ map (\n -> take (length l) $ drop n $ cycle l) [0..length l - 1]
where perm_main [x] = [[x]]
perm_main (x:xs) = map (x:) $ perm xs

isGraphical :: [Int] -> Bool
isGraphical [] = True
isGraphical (x:xs)
| x < 0 = False
| length xs < x = False
| otherwise =
or $ map ( \(ys, zs) -> isGraphical $ filter (/=0)
$ map (subtract 1) ys ++ zs) $ map (splitAt x) $ perm xs > >えーと解説します。 > >単純無向グラフはループ(自分自身への辺)が存在せず、辺の重複は許されない(同じノード対の間には高々1本の辺しかない)という性質がある。実は、あんまし考えずに最初っからその仮定でコードを組んで、後から「単純無向グラフって何だっけ？」と性質を調べたらそのようだったのでラッキーだったという話なんですが。 > >さて、このとき、たとえば > >この「残りの > >それから空列は真だし、どれかの要素が負値になることはありえない。また、先頭要素の値が残りの頂点数よりも大きい時は辺を張りきれないからグラフ的でない。 > >というところかな。いちおう動くみたいです。重いけど。かなり愚直な例だと思います。降順ソートすると速くなります。 > >追記: 筆写だったので typo を発見しました。とほほ。あと適当なところで改行しました。 > >追記2: >yanagiさんの解答 >
をみつつ、やっぱり comb を作った方が速いような気がしていた。なんで permutation にしたんだったかなあ。 List に標準で備わっているような気がしたからだろうか。というわけでその版。 > >mkComb :: Int -> Int -> [[Int]]
mkComb l 0 = [repeat 0]
mkComb l n
| l == n = [repeat (-1)]
| otherwise = map (-1:) (mkComb (l-1) (n-1)) ++ map (0:) (mkComb (l-1) n)
isGraphical :: [Int] -> Bool
isGraphical [] = True
isGraphical (x:xs)
| x < 0 = False
| length xs < x = False
| otherwise =
or $ zipWith (\ comb ys -> isGraphical $ filter (/=0) $
zipWith (+) comb ys) (mkComb (length xs) x) (repeat xs) > >こんなところでしょうか。こっちの方がやっぱ圧倒的に速いなあ。しょぼーん。 > >解説は略。というか本質的には同じです。 >

Category: Uncategorized
You can follow any responses to this entry via RSS.
Both comments and trackbacks are currently closed.

Comments are closed.