I have to write a Haskell function that gives all possible permutations of a given list.

The type signature has to be:

permutations :: [a] -> [[a]]

For example, an acceptable result is (under ghci):

λ>
λ> permutations [1,2,3]
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
λ> 

The following restrictions apply:

1. Plain lists are the sole authorized data structure, so no Set or Vector.
2. The permutations may be produced in any order.
3. The function must work for any element type, i.e. no Ord a or Eq a instances.
4. Only library functions from the standard Prelude may be used.

Does anyone know how I could do it ?

CodePudding user response：

There are several ways to approach this problem. jpmarinier suggest one possible way in the comments, but I think a recursive approach following the structure of the input list is more natural in Haskell.

For that recursive approach you have to implement what needs to happen in the case the list is empty and what needs to happen in the case that the list contains at least one element and in this case you can also use the function recursively on the rest of the list. The general structure is:

permutations [] = _
permutations (x:xs) = let xs' = permutations xs in _

The case with the empty list is pretty simple, but there are a few different choices that make the compiler happy, so it might not be immediately clear which one you should choose.

For the case with at least one element I would use a second helper function called splits :: [Int] -> [([Int],[Int])] which computes all possible splits of the input list into two lists.

Here an example input and output that might make it more clear what I mean:

splits [1,2,3] == [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]

The implementation of this function is also recursive and follows the same pattern:

splits [] = _
splits (x:xs) = let xs' = splits xs in _

CodePudding user response：

The Wikipedia article on permutations leads us to, among many other things, the Steinhaus–Johnson–Trotter algorithm, which seems well suited to linked lists.

For this algorithm, an essential building block is a function we could declare as:

spread :: a -> [a] -> [[a]]

For example, expression spread 4 [1,2,3] has to put 4 at all possible positions within [1,2;3], thus evaluating to: [[4,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]]. To get all permutations of [1,2,3,4], you just need to apply spread 4 to all permutations of [1,2,3]. And it is easy to write spread in recursive fashion:

spread :: a -> [a] -> [[a]]
spread x [] = [[x]]
spread x (y:ys) = (x:y:ys) : (map (y:) (spread x ys))

And permutations can thus be obtained like this:

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (x:xs) = concat (map (spread x) (permutations xs))