本来打算用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论坛