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

_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Reply via email to