Get all permutations of a list in Haskell

Question

I am trying to do this from scratch, without using a library outside of the standard library. Here is my code:

permutations :: [a] -> [[a]] permutations (x:xs) = [x] : permutations' xs where permutations' (x:xs) = (:) <$> [x] <*> split xs split l = [[x] | x <- l] 

The problem is that this spawns only one fork in non-deterministic computing. Ideally, I would like

 (:) <$> [x] <*> ((:) <$> [x] <*> ((:) <$> [x] <*> ((:) <$> [x] <*> xs))) 

But I can’t find a way to do this cleanly. My desired result is something like this:

 permutations "abc" -> ["abc", "acb", "bac", "bca", "cab", "cba"] 

How to do it?

Answer 1

Perhaps you should use existing code:

 import Data.List permutations [1,2,3,4] 

Answer 2

For a simple implementation without duplication of input

 permutations :: Eq a => [a] -> [[a]] permutations [] = [[]] permutations as = do a <- as let l = delete a as ls <- permutations l return $ a : ls 

Test:

 λ> permutations [1,2,3] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] λ> permutations "abc" ["abc","acb","bac","bca","cab","cba"] λ> 

Algorithm Reference

Answer 3

I would do it like this:

 select :: [a] -> [(a,[a])] select = select' id where select' _ [] = [] select' acc (a:r) = (a, acc r) : select' (acc . (a:)) r permutations [] = [[]] permutations l = do (a,r1) <- select l r2 <- permutations r1 return (a: r2) 

Answer 4

I'm relatively new to Haskell, but I have developed a very efficient permutation algorithm for JS . It almost surpasses the heap algorithm, but in JS array rotation is more expensive than the lazy Haskell iterate function over lists. So this one, unlike all the above answers, seems a lot more efficient.

The built-in Data.List.permutations is still 2 times higher than this, since I don’t know the Haskell performance limits at all. Maybe someone here can help me move this code forward a bit.

So, I have a helper function that returns a list of all the turns of the provided list. For instance,

rotations [1,2,3] will give [[1,2,3],[2,3,1],[3,1,2]]

accordingly, the perms function:

 rotations :: [a] -> [[a]] rotations xs = take (length xs) (iterate (\(y:ys) -> ys ++ [y]) xs) perms :: [a] -> [[a]] perms [] = [[]] perms (x:xs) = concatMap (rotations.(x:)) (perms xs) 

Edit: So, I was thinking about how to make the above code more efficient. OK lists in Haskell are linked lists, and unlike JavaScript, length is not a property that you can access in O (1), but O (n). This is a function that traverses the entire damned list, basically counting all the elements in the list. Therefore, it is very expensive if you reuse it. This is what we do with the take (length xs) command every time the rotate function is called. We literally call it millions of times if your input list is 10-11 units or more in length. Cutting it will bring huge savings. Then let's not calculate the length of the same length lists over over, but instead, just give it:

 rotations :: Int -> [a] -> [[a]] rotations len xs = take len (iterate (\(y:ys) -> ys ++ [y]) xs) 

Beautiful. Well, now we need to slightly modify our perms function, respectively:

 perms :: [a] -> [[a]] perms [] = [[]] perms il@ (x:xs) = concatMap ((rotations len).(x:)) (perms xs) where len = length il 

so obviously il now assigned i nput l ist and len caches its length. Now it’s beautiful and quite interesting, it’s faster than the default Data.List.permutations .

So far so good ... But now it is time to trick a little and make it even faster. One thing that I know, and as I just proved, in CS, caching is the best fuel for the algorithm. So what do we look for in the cache next? We can easily cache return values ​​for inputs like [x] , [x,y] and [x,y,z] and save some calculations. Do you want more speed ..? Then shamelessly cache [w,x,y,z] too. Check out the new code as a whole;

 rotations :: Int -> [a] -> [[a]] rotations len xs = take len (iterate (\(y:ys) -> ys ++ [y]) xs) perms :: [a] -> [[a]] perms [] = [[]] perms [x] = [[x]] perms (x:[y]) = [[x,y],[y,x]] perms (x:y:[z]) = [[x,y,z],[y,z,x],[z,x,y],[x,z,y],[z,y,x],[y,x,z]] perms il@ (x:xs) = concatMap ((rotations len).(x:)) (perms xs) where len = length il 

Any ideas are welcome ...

Answer 5

It is already in the standard base library, so there is no need to fight. If you really want to see how to do this, you can look at the source of this library.

Answer 6

Everything is better with monads:

 perm :: [a] -> [[a]] perm [] = return [] perm (x:xs) = (perm xs) >>= (ins x) where ins :: a -> [a] -> [[a]] ins x [] = [[x]] ins x (y:ys) = [x:y:ys] ++ ( map (y:) (ins x ys) ) 

So: you have a function that inserts a letter into a word, but it produces more than one word, so how to apply it recursively? >>= helps!