99 questions/Solutions/26
From HaskellWiki
(Difference between revisions)
(another solution without tails) |
|||
| Line 31: | Line 31: | ||
ys <- combinations (n-1) xs' | ys <- combinations (n-1) xs' | ||
return (y:ys) | return (y:ys) | ||
| + | </haskell> | ||
| + | |||
| + | Another solution that's slightly longer, but doesn't depend on <hask>tails</hask>: | ||
| + | |||
| + | <haskell> | ||
| + | -- We don't actually need this base case; it's just here to | ||
| + | -- avoid the warning about non-exhaustive pattern matches | ||
| + | combinations _ [] = [[]] | ||
| + | -- Base case--choosing 0 elements from any list gives an empty list | ||
| + | combinations 0 _ = [[]] | ||
| + | -- Get all combinations that start with x, recursively choosing (k-1) from the | ||
| + | -- remaining xs. After exhausting all the possibilities starting with x, if there | ||
| + | -- are at least k elements in the remaining xs, recursively get combinations of k | ||
| + | -- from the remaining xs. | ||
| + | combinations k (x:xs) = x_start ++ others | ||
| + | where x_start = [ x : rest | rest <- combinations (k-1) xs ] | ||
| + | others = if k <= length xs then combinations k xs else [] | ||
</haskell> | </haskell> | ||
Revision as of 04:58, 17 July 2010
(**) 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)
tails
-- We don't actually need this base case; it's just here to -- avoid the warning about non-exhaustive pattern matches combinations _ [] = [[]] -- Base case--choosing 0 elements from any list gives an empty list combinations 0 _ = [[]] -- Get all combinations that start with x, recursively choosing (k-1) from the -- remaining xs. After exhausting all the possibilities starting with x, if there -- are at least k elements in the remaining xs, recursively get combinations of k -- from the remaining xs. combinations k (x:xs) = x_start ++ others where x_start = [ x : rest | rest <- combinations (k-1) xs ] others = if k <= length xs then combinations k xs else []
