查看单个帖子
  #3 (permalink)  
旧 2008-05-16
liuxinyu 的头像
liuxinyu liuxinyu 当前离线
高级会员
 
注册日期: 2006-02-09
帖子: 311
文章: 49
liuxinyu 正向着好的方向发展
默认 回复: 递归版的排列算法

其实C++代码中核心部分就是generate函数。但是如果仔细看,会发现思路是不一样的。

一个是从首位开始依次尝试从n各方案中pick一个,其本质是递归版的“深度优先”搜索;这也是众多组合数学教科书上的样板方法。

另一个是从首位枚举所有方案和后继节点展开的结果组合(cons),我个人认为是“广度优先”,这是因为lazy求值的原因。

我完全没有比较C++和Haskell的意图。只是因为试图用lisp写这个算法时遇到了困难,所以拿熟悉的C++来打草稿,这也是为何所有的功能都亲自手动实现了一遍的原因,这样将来用lisp写时就几乎是照猫画虎了。好在这些辅助函数都不麻烦。

我还是觉得搜索到这个haskell的方法满有意思的,因为对比教科书上的方法,这个开阔了思路。一个自然而然的有趣题目就是,用C++实现一个list enumeration。这个会很有意思。

另外,看了一下haskell中delete x xs的源代码,也是中规中矩,并不复杂:
代码:
delete :: (Eq a) => a -> [a] -> [a] delete = deleteBy (==) -- | The 'deleteBy' function behaves like 'delete', but takes a -- user-supplied equality predicate. deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] deleteBy _ _ [] = [] deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
回复时引用此帖