递归版的排列算法

liuxinyu · #1 (**permalink**) 2008-05-11

本来打算用fp实现一个排列算法。思路不大清楚，就先用C++实现了一个，本质仍是递归的。

大致思路如下：求n个数中取出r个数的排列可以如下产生：
1. 生成第i位数字时，从[1..n]中选择一个j
2. 检查j是否已经在1到i-1位使用过了，若使用过，则重复1，否则另j为第i位的数字
3. 比较i是否等于r,若等于r，则找到了一个排列，打印输出；否则i+1，递归调用生成第i+1位数字。

代码如下：

代码:

#include <iostream>
#include <vector>

using namespace std;

bool contains(const vector<int>& res, int i){
  for(vector<int>::const_iterator it=res.begin(); it!=res.end(); ++it)
    if(*it==i)
      return true;
  return false;
}

void print_res(const vector<int>& res){
  for(vector<int>::const_iterator it=res.begin(); it!=res.end(); ++it)
    std::cout<<*it<<",";
  std::cout<<"\n";
}

void generate(const vector<int>& res, int i, int n, int r){
  for(int j=1; j<=n; ++j){
    if(!contains(res, j)){
      vector<int> new_res(res);
      new_res.push_back(j);
      if(i==r)
	print_res(new_res);
      else
	generate(new_res, i+1, n, r);
    }
  }
}

void permutation(int n, int r){
  vector<int> res;
  generate(res, 1, n, r);
}

int main(int, char**){
  permutation(5, 3);
}

运行结果为：
1,2,3,
1,2,4,
...
5,4,3,

然后我开始尝试用haskell实现纯fp排列算法。后来实在忍不住上网google了一下，看到这个算法[1]：

代码:

import Data.List

permutation [] = [[]]     
permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)]

我略微解释一下，这个算法是求某个list的全排列，而非n元素取r个元素的排列。这个算法相当于这样的数学描述：
排列 list 的结果是：
平凡情况：若待排列list为空，则结果为空；
一般情况：排列结果={x和后继部分ys，其中x属于list，后继部分ys属于对list中删除x后进行排列的结果}

举个例子，[1,2,3]的全排列结果是：
x为1或2或3,
ys为 [2,3]或[1,3]或[1,2]全排列
x和ys组合在一起就是最终结果。

这里利用了Haskell的list comprehension的语法包装，它其实是filter和map的组合。

有了一个全排列算法，n,r排列就很容易了：

代码:

permutation xs n r= if length xs <= n-r
	then [[]]
	else [x:ys | x <- xs, ys <- permutation (delete x xs) n r]

运行结果如下：
permutation [1..5] 5 3
[[1,2,3],[1,2,4],...,[5,4,3]]

这与最初的C++代码比，真是完全不同的思路了。

--
[1]来自：List comprehension和递归的巧妙结合 - Haskell - Tech - JavaEye论坛

tomato · #2 (**permalink**) 2008-05-14

这个例子并不能很好的解释haskell的强大
这里更多的是syntactic sugar
ML之类支持这种语法的都可以写的很简单

delete x xs这种操作对于有库支持的语言就很简单，比如c++/java都可以很方便的做到
如果没有库支持靠自己实现就很痛苦了，比如lisp/c

这个程序用c++写也很短，上面的c++程序也写得很复杂，其实很多东西不用手动写
contains直接用std的find就可以
对于print_res可以用for_each，如果你用boost的话也不用自己写一个function object了
其实你的hashell代码并没有管算法之外的输出，所以拿print_res来比较是不公平的

听说haskell强大的是它的type system，这个我就不懂了

liuxinyu · #3 (**permalink**) 2008-05-16

其实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

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式

LinkBacks (?) LinkBack to this Thread: http://www.cpper.com/c/t4857.html
作者	For	Type	日期
polytypic programming - TopLanguage \| Google	This thread	Refback	2008-06-26 11:33 AM
polytypic programming - TopLanguage \| Google Groups	This thread	Refback	2008-06-25 09:15 PM