[prev in list] [next in list] [prev in thread] [next in thread]
List: haskell
Subject: Re: [Haskell] String permutation
From: "Sukit Tretriluxana" <tretriluxana.s () gmail ! com>
Date: 2006-07-26 16:44:46
Message-ID: 8252533f0607260944v723d6713h9a58d9655b5e4ebb () mail ! gmail ! com
[Download RAW message or body]
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@student.chalmers.se> wrote:
>
> On 7/26/06, Sukit Tretriluxana <tretriluxana.s@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
>
[Attachment #3 (text/html)]
Thank you so much for all the responses. They really open my eyes how flexible and \
powerful Haskell is. <br><br>Ed<br><br><div><span class="gmail_quote">On 7/26/06, <b \
class="gmail_sendername">Sebastian Sylvan</b> <<a \
href="mailto:sylvan@student.chalmers.se"> sylvan@student.chalmers.se</a>> \
wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, \
204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">On 7/26/06, Sukit \
Tretriluxana <<a href="mailto:tretriluxana.s@gmail.com"> \
tretriluxana.s@gmail.com</a>> wrote:<br>> Dear expert \
Haskellers,<br>><br>> I am a newbie to Haskell and try to write several \
algorithms with it. One of<br>> them is the string permutation which generates all \
possible permutations <br>> using the characters in the string. For example, if I \
say,<br>><br>> permute "abc"<br>><br>> It will return the the \
result as<br>><br>> ["abc","acb","bca","bac","cab","cba"]
<br>><br>> And here is the program I came up \
with.<br>><br>> permute :: String -> [String]<br>> permute str \
= rotate str len len<br>> where len = length \
str<br>><br>> rotate :: String -> Int -> Int -> [String] <br>> \
rotate _ _ 0 = []<br>> rotate s 1 _ = [s]<br>> rotate (ch:chs) len rcnt \
=<br>> map (\x -> ch : x) (rotate chs (len-1) \
(len-1))<br>> ++<br>> rotate (chs \
++ [ch]) len (rcnt-1)<br>><br> > I am more than certain that this simple \
program can be rewritten to be more<br>> succinct and possibly more efficient \
using Haskell's features. So I would<br>> like to ask if any of you would kindly \
show me an example. <br>><br><br>I like the following definition for \
simplicity:<br><br>perms xs = [x:ps | x <- xs, ps <- perms \
(xs\\[x])]<br><br>It's all quite straightforward, basically take each item in the \
list,<br>compute the permutations of the *rest* of the list ( i.e. remove the<br>item \
from the list) and then put the item in front.<br><br>Now, this is pretty \
inefficient, so let's do some basic algebra here.<br>Rather than computing the \
item/rest-of-list pairs in the list<br>comprhension itself, we first separate it into \
a function (doing the <br>exact same thing, for now).<br><br>perms xs = [x : ps | \
(y,ys) <- selections xs, ps <- perms ys]<br>selections xs = [(x,xs\\[x]) | x \
<- xs]<br><br>So now, this does the same thing. But rather than going through each \
<br>item (x) and then computing the rest of the list (x\\[x]) directly, we<br>simply \
write a function (selections) which does this for us (i.e.<br>returns a list of pairs \
of the item and the rest of the list).<br><br>Now, let's rewrite selections in a more \
efficient way: <br><br>selections [] = []<br>selections \
(x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- selections xs]<br><br>It's clear that the \
first (most straightforward) selection we can do<br>here here is the head and the \
tail of the list, (x,xs). Now we just <br>recursively compute the selections of the \
tail, and re-insert the head<br>in its rightful position at the front of the list \
part of each result.<br><br>So there you have it. A nice looking and fairly efficient \
way of<br> generating permutations, and the steps needed to come up with \
it.<br><br><br>/S<br>--<br><br>Sebastian Sylvan<br>+46(0)736-818655<br>UIN: \
44640862<br></blockquote></div><br>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic