Combinations

Combinations.hs

{-# LANGUAGE ExplicitForAll #-}

module Combinations (combinations) where

import Control.Arrow ((&&&))
import Control.Monad (replicateM)
import Control.Monad.State (StateT (StateT), evalStateT)
import Data.List (uncons, unfoldr)

unconses :: forall a. [a] -> [(a, [a])]
unconses = unfoldr (((id &&& snd) <$>) . uncons)

combinations :: forall a. Int -> [a] -> [[a]]
combinations n = evalStateT (replicateM n (StateT unconses))

-- |
-- >>> choose n k = product (take k [n, (n - 1) .. 1]) `div` product [1 .. k]
-- >>> 52 `choose` 5
-- 2598960
-- >>> (id &&& length) (combinations 5 [1..52])
-- ([[1,2,3,4,5],[1,2,3,4,6], ... ,[48,49,50,51,52]], 2598960)