haskellで組合せと順列

まさか…　そんなまさか…　さっき id:nobsun さんに教えてもらった

[(i,j)|i<-[1..10],j<-[i+1..10]]

が組合せだったなんて…

Prelude> mapM_ print $ map (\x->[(i,j)|i<-[1..x],j<-[i+1..x]]) [2..6]
[(1,2)]
[(1,2),(1,3),(2,3)]
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
[(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]
[(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)]

そりゃ、haskellのData.Listにcombinationsがないはずだ…

ちなみに3項だと

Prelude> mapM_ print $ map (\x->[(i,j,k)|i<-[1..x],j<-[i+1..x],k<-[j+1..x]]) [3..5]
[(1,2,3)]
[(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
[(1,2,3),(1,2,4),(1,2,5),(1,3,4),(1,3,5),(1,4,5),(2,3,4),(2,3,5),(2,4,5),(3,4,5)]

やべえ、もしかして順列もこれでできる？5P2は…

Prelude> [(i,j)|i<-[1..5],j<-[1..5],i/=j]
[(1,2),(1,3),(1,4),(1,5),(2,1),(2,3),(2,4),(2,5),(3,1),(3,2),(3,4),(3,5),(4,1),(4,2),(4,3),(4,5),(5,1),(5,2),(5,3),(5,4)]
Prelude> length [(i,j)|i<-[1..5],j<-[1..5],i/=j]
20

単なる直積の重複排除かよorz
まあ、項数限定だからpermutationsにはそれなりに意味があるな。

ちなみに以下の二つも同じだな。でもたぶん下の方が速い。haskellのtime関数がわからない…

Prelude> length [(i,j)|i<-[1..100],j<-[1..100],i<j]
4950
Prelude> length [(i,j)|i<-[1..100],j<-[i+1..100]]
4950