{-|

Module      : Permutation
Description : Some alternative permutation functions
Copyright   : © Frank Jung, 2020
License     : GPL-3

From the book
<http://www.cs.ox.ac.uk/publications/books/adwh Algorithm Design with Haskell by R. Bird and J. Gibbons>.

-}

module Permutation (inserts, perms1, perms2, perms3, picks) where

-- | Generate permutations using list comprehensions.
--
-- Example:
--
-- >>> perms1 "abc"
-- ["abc","bac","bca","acb","cab","cba"]
perms1 :: [a] -> [[a]]
perms1 :: forall a. [a] -> [[a]]
perms1 []     = [[]]
perms1 (a
x:[a]
xs) = [[a]
zs | [a]
ys <- [a] -> [[a]]
forall a. [a] -> [[a]]
perms1 [a]
xs, [a]
zs <- a -> [a] -> [[a]]
forall a. a -> [a] -> [[a]]
inserts a
x [a]
ys]

-- | Insert character into list at each location.
--
-- Example:
--
--  >>> inserts 'a' "bc"
--  ["abc","bac","bca"]
inserts :: a -> [a] -> [[a]]
inserts :: forall a. a -> [a] -> [[a]]
inserts a
x []     = [[a
x]]
inserts a
x (a
y:[a]
ys) = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys) [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (a -> [a] -> [[a]]
forall a. a -> [a] -> [[a]]
inserts a
x [a]
ys)

-- | Generate permutations using list comprehensions.
--
-- Example:
--
-- >>> perms2 "abc"
-- ["abc","acb","bac","bca","cab","cba"]
perms2 :: [a] -> [[a]]
perms2 :: forall a. [a] -> [[a]]
perms2 [] = [[]]
perms2 [a]
xs = ((a, [a]) -> [[a]]) -> [(a, [a])] -> [[a]]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (a, [a]) -> [[a]]
forall {a}. (a, [a]) -> [[a]]
subperms ([a] -> [(a, [a])]
forall a. [a] -> [(a, [a])]
picks [a]
xs)
  where subperms :: (a, [a]) -> [[a]]
subperms (a
y,[a]
ys) = ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [[a]]
forall a. [a] -> [[a]]
perms2 [a]
ys)

-- | Pick each member from list return tuple of member and items remaining.
--
-- Example:
--
-- >>> picks "abc"
-- [('a',"bc"),('b',"ac"),('c',"ab")]
picks :: [a] -> [(a, [a])]
picks :: forall a. [a] -> [(a, [a])]
picks []     = []
picks (a
x:[a]
xs) = (a
x,[a]
xs) (a, [a]) -> [(a, [a])] -> [(a, [a])]
forall a. a -> [a] -> [a]
: [(a
y,a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys) | (a
y,[a]
ys) <- [a] -> [(a, [a])]
forall a. [a] -> [(a, [a])]
picks [a]
xs]


-- | Use fold to generate permutaions.
perms3 :: [a] -> [[a]]
perms3 :: forall a. [a] -> [[a]]
perms3 = (a -> [[a]] -> [[a]]) -> [[a]] -> [a] -> [[a]]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (([a] -> [[a]]) -> [[a]] -> [[a]]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (([a] -> [[a]]) -> [[a]] -> [[a]])
-> (a -> [a] -> [[a]]) -> a -> [[a]] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> [a] -> [[a]]
forall a. a -> [a] -> [[a]]
inserts) [[]]