Skip to content

Instantly share code, notes, and snippets.

@bradparker
Created July 8, 2021 05:41
Show Gist options
  • Save bradparker/4ce928a885845b486cb604eb6f29612d to your computer and use it in GitHub Desktop.
Save bradparker/4ce928a885845b486cb604eb6f29612d to your computer and use it in GitHub Desktop.
Combinations
{-# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment