Haskell 实现全排列

用Haskell语言实现一个全排列，我们使用递归的思想：

定义这个函数名为permute :: [a] -> [[a]]，对于一个数组s :: [a]，从中取出第1个元素x，并且得到剩下元素xs的全排列as :: [[a]], as = permute xs，那么我们从as中任意取一个排列a，将x插入到a中的任意一个位置（包括首尾）。代码如下：

-- permute: give a list and return a arrangement list
permute :: [a] -> [[a]]
permute [] = []
permute (x:[]) = [[x]]
permute (x:xs) = let as = permute xs
                     n  = length xs
                 in  [ insertElem x i a  | i <- [0..(length xs)], a <- as ]

insertElem x n xs = take n xs ++ (x:(drop n xs))

列出集合的所有对换也是很重要的，参考代码如下：

pairs :: [a] -> [(a,a)]
pairs [] = []
pairs (x:[]) = []
pairs (x:xs) = [(x,y') | y' <- xs] ++ pairs xs