[Haskell] String permutation

[Sukit Tretriluxana]

Thank you so much for all the responses. They really open my eyes how
flexible and powerful Haskell is.

Ed

On 7/26/06, Sebastian Sylvan <sylvan at student.chalmers.se> wrote:
>
> On 7/26/06, Sukit Tretriluxana <tretriluxana.s at gmail.com> 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"]
> >
> > And here is the program I came up with.
> >
> >  permute :: String -> [String]
> > permute str = rotate str len len
> >    where len = length str
> >
> > rotate :: String -> Int -> Int -> [String]
> > rotate _ _ 0 = []
> > rotate s 1 _ = [s]
> > rotate (ch:chs) len rcnt =
> >    map (\x -> ch : x) (rotate chs (len-1) (len-1))
> >    ++
> >    rotate (chs ++ [ch]) len (rcnt-1)
> >
> > 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.
> >
>
> I like the following definition for simplicity:
>
> perms xs = [x:ps | x <- xs, ps <- perms (xs\\[x])]
>
> It's all quite straightforward, basically take each item in the list,
> compute the permutations of the *rest* of the list (i.e. remove the
> item from the list) and then put the item in front.
>
> Now, this is pretty inefficient, so let's do some basic algebra here.
> Rather than computing the item/rest-of-list pairs in the list
> comprhension itself, we first separate it into a function (doing the
> exact same thing, for now).
>
> perms xs = [x : ps | (y,ys) <- selections xs, ps <- perms ys]
> selections xs = [(x,xs\\[x]) | x <- xs]
>
> So now, this does the same thing. But rather than going through each
> item (x) and then computing the rest of the list (x\\[x]) directly, we
> simply write a function (selections) which does this for us (i.e.
> returns a list of pairs of the item and the rest of the list).
>
> Now, let's rewrite selections in a more efficient way:
>
> selections []     = []
> selections (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- selections xs]
>
> It's clear that the first (most straightforward) selection we can do
> here here is the head and the tail of the list, (x,xs). Now we just
> recursively compute the selections of the tail, and re-insert the head
> in its rightful position at the front of the list part of each result.
>
> So there you have it. A nice looking and fairly efficient way of
> generating permutations, and the steps needed to come up with it.
>
>
> /S
> --
>
> Sebastian Sylvan
> +46(0)736-818655
> UIN: 44640862
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell/attachments/20060726/26c6e928/attachment.htm