[Haskell] String permutation

[Martin Erwig]

On Jul 26, 2006, at 6:59 AM, Robert Dockins wrote:

>
> On Jul 26, 2006, at 12:44 AM, Sukit Tretriluxana wrote:
>
>> Dear expert Haskellers,
>>
>> I am a newbie to Haskell and try to write several algorithms with  
>> it. One of them is the string permutation which generates all  
>> possible permutations using the characters in the string. For  
>> example, if I say,
>>
>> permute "abc"
>>
>> It will return the the result as
>>
>> ["abc","acb","bca","bac","cab","cba"]
>>
>
> [snip]
>
> > I am more than certain that this simple program can be rewritten  
> to be more succinct and possibly more efficient using Haskell's  
> features. So I would like to ask if any of you would kindly show me  
> > an example.
>
>
> About the shortest way I can think of, using the good ol' list  
> monad.  This isn't exactly efficient, but there you are...
>
>
> import Data.List
>
> permute :: String -> [String]
> permute [] = [[]]
> permute str = do
>    x  <- str
>    xs <- permute (delete x str)
>    return (x:xs)

Or using list comprehensions and generalizing the type:


permute :: Eq a => [a] -> [[a]]
permute [] = [[]]
permute xs = [x:ys | x <- xs, ys <- permute (delete x xs)]


Or making it completely polymorphic by replacing delete:


permute :: [a] -> [[a]]
permute [] = [[]]
permute xs = [x:zs | (x,ys) <- expose xs, zs <- permute ys]
              where expose xs = step [] xs
                    step _  []     = []
                    step ys (x:xs) = (x,ys++xs):step (ys++[x]) xs


--
Martin