val it: α → α = fun

mkComb :: Int -> Int -> [[Int]]
mkComb l 0 = [take l $ repeat 0]
mkComb l n
| l == n = [take l $ 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 (-) ys comb) (mkComb (length xs) x) (repeat xs)

genGraphical :: [Int] -> [[Int]]
genGraphical l = map addNewNode $ concat $ map (mkComb (length l)) [0..length l]
where addNewNode comb =
let n = length $ filter (==1) comb in
sort $ n : zipWith (+) l comb

unfoldr2 :: (a -> a) -> a -> [a]
unfoldr2 f x = x : unfoldr2 f (f x)

graphicals :: [[Int]]
graphicals = concat $ unfoldr2 (nub . concat . map genGraphical) [[0]] > >*Main> take 20 graphicals
[[0],[0,0],[1,1],[0,0,0],[0,1,1],[1,1,2],[2,2,2],[0,0,0,0],[0,0,1,1],[0,1,1,2],[1,1,1,3],[1,1,1,1],[1,1,2,2],[0,2,2,2],[1,2,2,3],[2,2,2,2],[2,2,3,3],[3,3,3,3],[0,0,0,0,0],[0,0,0,1,1]] > >ざっとこんな感じ。ところで単純無向グラフって連結でないといけないんだっけ？　だとするとまずいな。あとで調べます。 > >このアルゴリズムは、長さ l のグラフ的なリストから長さ l+1 なグラフ的なリストを生成している(genGraphical)。ようするに新しいノードを追加してリンクを追加すればいいわけで、これは mkComb を使えば isGraphical で「ノードを削ってリンクを削除」の逆操作となる。それならそれでもうちょっと綺麗な書き方もある気もするけれど。 > >それはともかく、それですべてを拾えるということはかならずしも自明でない気がする。ただし、ある単純無向グラフの部分グラフは常に単純無向グラフだし、ノード数の少ない場合の単純無向グラフはすべて列挙しきっていることは確認できる。そこから帰納的に任意の長さlに対してこの方法ですべてのグラフを列挙できる気がする。 > >別のアプローチとしてこんなのもあるかもしれない。長さ l のリストがグラフ的であるためには、すくなくとも各要素の値が 0 以上 l 未満でないといけない。なぜなら長さ l のリストは頂点数が l なので、l本の辺が一本の頂点から出ると必ずループか多重辺を含むから。そのような条件を列挙するのは簡単で、 l 次元空間の格子点列挙問題に帰着できる。あとは isGraphical でフィルタリングしてやればいい。 > >というのはこんな感じかな？(普通の格子点列挙とは違うアプローチになってますが)。 > >lattices :: Int -> Int -> [[Int]]
lattices 0 _ = [[]]
lattices n b = [ x : xs | x <- [0..b], xs <- lattices (n-1) b]

graphicals2 :: [[Int]]
graphicals2 = concat $ map (\l -> filter isGraphical $ nub $ map sort $ lattices l (l-1)) [1..] > >むろんこっちの方が効率は悪いです。 >