0

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 ?

Improve this question
5
  • 1
    There is a concept of “the next permutation” after the current one. See the C++ version of it for example. The next permutation may exist, or not. For example, your [3,2,1] is the one having no successor in the lexicographic order. Now, say if you wrote first a nextPermutation :: [Int] -> Maybe [Int] building block, you might be able to come up with a recursive version of your permutations function. Commented Dec 21, 2021 at 18:18
  • 1
    Very often, recursion is used (although not per se explicitly). You thus can first try to implement a function that performs the permutation of 0 elements, 1 element, 2 elements, and then solve the problem with n elements in terms of n-1 elements. Commented Dec 21, 2021 at 18:29
  • If Vector and Set data types are disallowed, the Steinhaus–Johnson–Trotter algorithm seems convenient. Commented Dec 22, 2021 at 11:28
  • Within the SJT algorithm, an essential building block is the spread function. Expression spread 4 [1,2,3] puts 4 at all possible positions within [1,2;3] : [[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 use spread 4 on all permutations of [1,2,3]. So you have a base case: permutations [] = [[]] and a compound case: permutations (x:xs) = concat (map (spread x) (permutations xs)) . And it is not that difficult to write a recursive implementation of function spread. Commented Dec 22, 2021 at 22:34
  • This question is very similar to a later one. Commented Dec 24, 2021 at 10:44

2 Answers 2

Reset to default
2

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 _
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Why do you think there's more than one sensible answer for the empty list? All signs point to one specific answer.
There is one conventional answer, but I think it is easy to make the "mistake" of picking the "wrong" answer. Nevertheless, I think rewording it from "sensible" to "makes the compiler happy" avoids this issue, thanks.
0

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))
Improve this answer

1 Comment

Note: this answer is derived from an answer to a later, similar question which was written while the current question happened to be temporarily under a “Closed” status.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.