Combination
To find the combination of (n,r), we can use this formula:
C(n,r) = C(n-1,r-1) + C(n-1,r)
This means, combination of (n,r) equals to combine of
take the first ( C(n-1,r-1) ) and without take the first ( C(n-1,r) ).
For example, for C(2,1), it can be:
C(2,1)
= add#1 in C(1,0) + C(1,1)
= add#1 in C(1,0) + add#2 in C(0,0) + C(0,1)
where
add#1 = add first element of list ( C(2,1) )
add#2 = add first element of list ( C(1,1) )
So, the base case could define as:
C(_,0) = [[]]
C(0,_) = []
Here is the Haskell definition for combination:
combination :: [a] -> Int -> [[a]]
combination _ 0 = [[]]
combination [] _ = []
combination (x:xs) n = map (x:) (combination xs (n-1)) ++ combination xs n