Search code examples
haskellsubsetbinomial-coefficients

Combs on a large set doesn't compute Haskell


I'm writing a combs function in haskell what it needs to do is, when I provide it with a deck of cards, give me every combination of hands possible from that deck of size x

This is the relevant code

combs :: Int -> [a] -> [[a]]
combs 0 _      = [[ ]]
combs i (x:xs) =  (filter (isLength i) y)
            where y = subs (x:xs)
combs _ _      = [ ]

isLength :: Int -> [a] -> Bool
isLength i x
        | length x == i = True
        | otherwise     = False

subs :: [a] -> [[a]]
subs [ ] = [[ ]]
subs (x : xs) = map (x:) ys ++ ys
            where ys = subs xs

However, when I ask it to compute a combs 5 [1..52], e.g. a hand of 5 out of a full deck, it does not provide a result, and keeps running for a really long time
Does anyone know what the problem is and how to speed up this algorithm?


Solution

  • To extract i items from x:xs you can proceed in two ways:

    • you keep the x, and extract only i-1 elements from xs
    • you discard x, and extract all the i elements from xs

    Hence, a solution is:

    comb :: Int -> [a] -> [[a]]
    comb 0 _      = [[]]  -- only the empty list has 0 elements
    comb _ []     = []    -- can not extract > 0 elements from []
    comb i (x:xs) = [ x:ys | ys <- comb (i-1) xs ]  -- keep x case
                    ++ comb i xs                    -- discard x case
    

    By the way, the above code also "proves" a well-known recursive formula for the binomial coefficients. You might already have met this formula if you attended a calculus class. Letting B(k,n) = length (comb k [1..n]), we have

    B(k+1,n+1) == B(k,n) + B(k+1,n)
    

    which is just a direct consequence of the last line of the code above.