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