{- |
Description: Combinations
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P26" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P26 (combinations) where

{- |
Generate the combinations of \(k\) distinct objects chosen from the \(n\) elements of a list.
-}
combinations :: Int -> [a] -> [[a]]
combinations :: forall a. Int -> [a] -> [[a]]
combinations Int
0 [a]
_      = [[]]
combinations Int
_ []     = []
combinations Int
1 [a
x]    = [[a
x]]
combinations Int
n (a
x:[a]
xs) = Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinations Int
n [a]
xs [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a
x:) (Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinations (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) [a]
xs)