99 questions/Solutions/26
From HaskellWiki
(type signature) 

(6 intermediate revisions by 5 users not shown) 
Latest revision as of 19:40, 18 January 2014
(**) 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 wellknown 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 'n1' 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 (n1) xs']  Alternate syntax, using 'do'notation combinations :: Int > [a] > [[a]] combinations 0 _ = return [] combinations n xs = do y:xs' < tails xs ys < combinations (n1) xs' return (y:ys)
combinations :: Int > [a] > [[a]] combinations 0 _ = [[]] combinations n xs = [ xs !! i : x  i < [0..(length xs)1] , x < combinations (n1) (drop (i+1) xs) ]
combinations :: Int > [a] > [[a]]  We don't actually need this base case; it's just here to  avoid the warning about nonexhaustive pattern matches combinations _ [] = [[]]  Base casechoosing 0 elements from any list gives an empty list combinations 0 _ = [[]]  Get all combinations that start with x, recursively choosing (k1) 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 (k1) xs ] others = if k <= length xs then combinations k xs else []
Variant: This version avoids getting a result consisting of the empty choice if we ask for, say, 10 elements from the empty list. (Instead, an empty list, suggesting "no options available" is returned.)
combinations :: Int > [a] > [[a]] combinations 0 _ = [[]] combinations _ [] = [] combinations n (x:xs) = (map (x:) (combinations (n1) xs)) ++ (combinations n xs)
A solution using subsequences in Data.List
combinations k ns = filter ((k==).length) (subsequences ns)
A funny solution using Applicative in Control.Applicative. Funny because it's the opposite of other solutions. The idea is to generate all possible combinations by allowing permutations and by allowing multiple instances of one value in the list. Then we filter the list to stick with the exercice.
 let's try it with combinations 2 [1,2,3] combinations :: (Ord a) => Int > [a] > [[a]] combinations n xs = compressed where  create all combinations (multiple instances, permutations allowed)  answer : [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]] combinations' n _  n <= 0 = [[]] combinations' 1 xs = map (:[]) xs combinations' n xs = (:) <$> xs <*> combinations (n1) xs  sort every sublist and the list itself after that  [[1,1],[1,2],[1,2],[1,3],[1,3],[2,2],[2,3],[2,3],[3,3]] sorted = sort . map sort $ combinations' n xs  for each sublist, eliminate duplicates (see Problem 8)  [[1],[1,2],[1,2],[1,3],[1,3],[2],[2,3],[2,3],[3]] grouped = map (map head . group) sorted  filter all sublist with length < n,  this means that they had at least two times the same value in it  [[1,2],[1,2],[1,3],[1,3],[2,3],[2,3]] filtered = filter (\xs > length xs == n) grouped  eliminate duplicates a second time, this time in the list itself  [[1,2],[1,3],[2,3]] compressed = map head . group $ filtered
The long list of variables in the where clause are there for educational purpose.