Permutation, Repeated permutation, Combination

-- Permutation (순열)
nPr :: [a] -> Int -> [[a]]
nPr xs r
    | r < 0            = error "r must be above zero"
    | r > length xs = error "r must be below length of list"
    | null xs        = error "empty list is not accepted"
    | otherwise     = filter (\x -> length x == r) $ concatMap permutations $ subsequences xs

For Pointfree Style.
\x -> length x == r
<==> (r ==) . length




-- Repeated permutation (중복순열)
-- nub를 filter와 subsequences 사이에 넣으면 느려짐. d/t nub ~ O(n^2)
nTr :: Eq a => [a] -> Int -> [[a]]
nTr xs r
    | r < 0        = error "r must be above zero"
    | null xs    = error "empty list is not accepted"
    | otherwise = nub $ filter (\x -> length x == r) $ subsequences $ concat $ replicate r xs


-- Combination (조합)
nCr :: [a] -> Int -> [[a]]
nCr xs r
    | r < 0            = error "r must be above zero"
    | r > length xs = error "r must be below length of list"
    | null xs         = error "empty list is not accepted"
    | otherwise     = filter (\x -> length x == r) $ subsequences xs