ABCDEFG-GFEDCBA

如果你不敢去做，你会找到一个理由...

如果你不敢去做，你会找到一个理由
如果你决定要做，你会找到一个方法

(pbxy@newSMTH)

Data Path logic cells

对n-bit的data bus进行运算的logic cell。
输入(bus)，输出(bus)，控制信号

如何在haskell里实现permute(NewSMTH)

发信人: faint (faint), 信区: FuncProgram
标 题: 转载: 如何在haskell里实现permute
发信站: 水木社区 (Thu Jul 27 01:05:22 2006), 站内

[Haskell] String permutation haskell

Sukit Tretriluxana
to haskell
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
_______________________________________________

CHA Reeseo
to haskell

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/

_______________________________________________

Martin Percossi
to Sukit, haskell
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
_______________________________________________

Tomasz Zielonka
to Sukit, haskell
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
- Show quoted text -
_______________________________________________

Robert Dockins
to Sukit, haskell
On Jul 26, 2006, at 12:44 AM, Sukit Tretriluxana wrote:

[snip]


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
- Show quoted text -

_______________________________________________

Martin Erwig
to Robert, haskell

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
- Show quoted text -

_______________________________________________

Sebastian Sylvan
to Sukit, haskell
- Show quoted text -

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
- Show quoted text -
_______________________________________________
javascript:void(0)
发布
Sukit Tretriluxana
to Sebastian, haskell
More options 12:44 pm(16 minutes ago)
Thank you so much for all the responses. They really open my eyes how flexible and powerful Haskell is.

Ed

※ 来源:·水木社区 newsmth.net·[FROM: 24.193.243.*]

Haskell版本的快速排序

From
qsort [] = []
qsort (x:xs) = qsort (filter (<>= x) xs)

List comprehesion
qsort [] = []
qsort (x: xs) = (qsort left_xs) ++ [x] ++ (qsort right_xs)
where
left_xs = [y| y <- xs, y <= x]
right_xs = [y| y <- xs, y > x]
是不是很接近数学描述呢，呵呵

我

轮滑，游泳，Emacs，Linux。
继续想

IDEA收集

序幕写上“VRMM xx年” － by洪晶
（注：参照高达系列的风格）

小草

K歌
乒乓球，羽毛球，跳舞
吃东西