[Haskell] String permutation

[Tomasz Zielonka]

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