permutations.hs

permutations.hs

-- Adapted from https://gist.github.com/EmmanuelOga/18873d5f34bc4a5e3d10

-- insert elem on a list at the i position
-- pinsert 7 [1,2] 1 -> [1,7,2]
pinsert :: a -> [a] -> Int -> [a]
pinsert e xs i = (take i xs) ++ [e] ++ (drop i xs)

-- intersperce an elem in all posible places of a list
-- ex.: pinters 1 [2, 3] -> [[1,2,3], [2, 1, 3], [2, 3, 1]]
pinters :: a -> [a] -> [[a]]
pinters e xs = map (pinsert e xs) [0..length xs]

-- return a list of lists that results of putting elem in every possible position of each of the lists.
--     combine 5, [[1,2], [3,4]]
--  produces:
--     [ [ 5, 1, 2 ], [ 1, 5, 2 ], [ 1, 2, 5 ], [ 5, 3, 4 ], [ 3, 5, 4 ], [ 3, 4, 5 ] ]
pcombine :: a -> [[a]] -> [[a]]
pcombine e xss = concat $ map (pinters e) xss

-- return every permutation of the values of the list
pperms :: [a] -> [[a]]
pperms [] = [[]]
pperms (x:xs) = pcombine x (pperms xs)