Haskell::組み合わせの生成(2要素)

Haskellで比較的小さな集合からの組み合わせのセットを生成するには、list comprehensionを使えば一発で記述できる。

GHCi, version 6.8.3: http://www.haskell.org/ghc/  😕 for help
Loading package base … linking … done.
Prelude> [[x,y]|x<-[1..10],y<-[1..10],x<y]
[[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[2,10],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[3,10],[4,5],[4,6],[4,7],[4,8],[4,9],[4,10],[5,6],[5,7],[5,8],[5,9],[5,10],[6,7],[6,8],[6,9],[6,10],[7,8],[7,9],[7,10],[8,9],[8,10],[9,10]]

この場合は10要素の集合から2要素取り出す場合の組み合わせのリストになる。
全ての組み合わせが必ずしもいらない場合や、無限集合からの場合はそれなりにコードを書かないといけない。

で、2要素を取り出す組み合わせを無限リストとして返すコードを書いてみる。

 

-- comb2.hs
import List;
main = putStrLn $ unwords $ map show $ take 100 $ comb2 1
comb2 :: Int -> [[Int]]
comb2 n
| n<2         = comb2 2
| otherwise   = let {
s1 = transpose [[1..n], reverse [1..n]];
s2 = filter (\cs -> (nth 1 cs) < (nth 2 cs)) s1;
} in s2 ++ comb2 (n + 1)
nth :: Int -> [a] -> a
nth n s
| n<=1        = head s
| otherwise   = nth (n - 1) (tail s)
--

x>0, y>0の平面をy=-x+aに沿ってスキャンし、aを順次増加させていくようなイメージですかね。

例によって、main で take の引数の数を変えてやれば、いくらでも組み合わせを得ることができる。

寒っ

つい先日まで室内ではTシャツ+ハーフパンツで過ごしてたのに、昨晩はさすがに寒くてトレーナを引っ張り出した。
今朝も寒さを感じて目が覚めたし。

さすがに、師走だねぇ。