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. Regards, Ed
On Wednesday 26 July 2006 13:44, 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"]
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.
Sorry for my rough English. How about this? This is just ANOTHER way which is not so succincter or more efficient than yours. :) (.^) = (.) . (.) -- (.^) uf bf x y = uf (bf x y) (.^^) = (.) . (.) . (.) -- (.^^) uf tf x y z = uf (tf x y z) (^.) = (.) . flip (.) -- (^.) f g = (. f) . g shuffle :: [a] -> [[a]] shuffle [] = [[]] shuffle (x:xs) = concatMap (insertAll x) (shuffle xs) where insertAll :: a -> [a] -> [[a]] insertAll e [] = [[e]] insertAll e (x:xs) = (e:x:xs) : map (x:) (insertAll e xs) combine, permute :: [a] -> Integer -> [[a]] combine _ r | r < 0 = error "Zero or more elements should be extracted." combine _ 0 = [[]] combine [] _ = [] combine (x:xs) r = map (x:) (combine xs (r - 1)) ++ combine xs r permute = concatMap shuffle .^ combine Please note that I'm using different names from yours. The function "shuffle" above means so-called "full shuffle" which may be similar to your "permute" function, and my "combine" and "permute" generate all the cases of nCr and nPr, respectively. -- CHA Reeseo http://www.reeseo.net/
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.
While I could hardly be called an expert haskeller, here's my version: permute :: [a] -> [[a]] permute [] = [[]] permute list = concat $ map (\(x:xs) -> map (x:) (permute xs)) (take (length list) (unfoldr (\x -> Just (x, tail x ++ [head x])) list)) HTH Martin
On Tue, Jul 25, 2006 at 09:44:36PM -0700, Sukit Tretriluxana wrote:
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)
Some notes: Your permute gives 0 permutations for an empty input String, but there should be 1 - the empty string. Note that 0! == 1 The name "rotate" suggests that this function does less than it actually does. Also, your functions could easily work for lists with other types of values, not only for [Char], but you unneccesarily restrict their types.
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.
There are some examples at http://www.haskell.org/hawiki/PermutationExample Below is my favourite way to compute permutations. import List perms [] = [[]] perms (x:xs) = [ p ++ [x] ++ s | xs' <- perms xs , (p, s) <- zip (inits xs') (tails xs') ] It's not too efficient - there are other versions that exhibit better sharing of list tails, etc. Also, the resulting list is not lexicographically ordered (when the input one is sorted). But I like the look of this code. Best regards Tomasz
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) Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
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
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
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
participants (7)
-
CHA Reeseo -
Martin Erwig -
Martin Percossi -
Robert Dockins -
Sebastian Sylvan -
Sukit Tretriluxana -
Tomasz Zielonka