99 questions/Solutions/26
< 99 questions | Solutions
Jump to navigation
Jump to search
(**) Generate the combinations of K distinct objects chosen from the N elements of a list
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.
-- Import the 'tails' function
-- > tails [0,1,2,3]
-- [[0,1,2,3],[1,2,3],[2,3],[3],[]]
import Data.List (tails)
-- The implementation first checks if there's no more elements to select,
-- if so, there's only one possible combination, the empty one,
-- otherwise we need to select 'n' elements. Since we don't want to
-- select an element twice, and we want to select elements in order, to
-- avoid combinations which only differ in ordering, we skip some
-- unspecified initial elements with 'tails', and select the next element,
-- also recursively selecting the next 'n-1' element from the rest of the
-- tail, finally consing them together
-- Using list comprehensions
combinations :: Int -> [a] -> [[a]]
combinations 0 _ = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
, ys <- combinations (n-1) xs']
-- Alternate syntax, using 'do'-notation
combinations :: Int -> [a] -> [[a]]
combinations 0 _ = return []
combinations n xs = do y:xs' <- tails xs
ys <- combinations (n-1) xs'
return (y:ys)