在Haskell中递归排列
我正试图实施用于生成排列的Steinhaus-Johnson-Trotter算法。 我的代码如下：
permutations :: [a] -> [[a]]
permutations [] = []
permutations (x:[]) = [[x]]
permutations xs = [ys ++ [xs !! i] | i <- [len,len-1..0], ys <- permutations (delete i xs)]
where len = (length xs)
delete i xs = take i xs ++ drop (succ i) xs
这是Python代码的直接翻译：
def perms(A):
if len(A)==1:
yield A
for i in xrange(len(A)-1,-1,-1):
for B in perms(A[:i]+A[i+1:]):
yield B+A[i:i+1]
Python代码有效，但Haskell代码进入无限递归。 列表理解中的permutations (delete i xs)应该使流程更接近基本情况。 为什么无限递归发生？
编辑： @augustss说：
当你有一个函数超过列表的多个基本情况时，一定要小心。
所以我改变了基本情况
permutations [] = []
permutations (x:[]) = [[x]]
更简单
permutations [] = [[]]
你的循环不一样。
i <- [len,len-1..0]
VS
for i in xrange(len(A)-1,-1,-1):
该第一个情况下，你结合i的长度，而不是长度减一。 结果是delete i xs返回xs ，所以你得到无限递归。
我也有一些附注。
先!! 是线性时间。 你最好写一个帮手功能，结合起来!! ， delete以及将输入迭代到一个列表遍历中。 就像select :: [a] -> [(a, [a])] 。 你可以高效地做到这一点。
其次， ++也是线性时间。 使用它将单个元素附加到现有列表很慢。 如果你的目标是产生所有的排列，而不是它们的特定顺序，你应该使用(xs !! i) : ys作为返回的表达式。 （对第一点做出的任何更改进行适当修改。）
select
基于@ Carl的回答，我实现了select :: [a] -> [(a, [a])]函数。 它的任务是生成元组列表(a, [a]) ，其中元组的第一部分是列表中的元素，而元组的第二部分是列表中除元素外的所有元素。
select :: [a] -> [(a, [a])]
select [] = []
select (x:xs) = select' x [] xs
where
select' x left [] = [(x, left)]
select' x left right@(r:rs) = (x, left++right) : select' r (x:left) rs
但是我发现在Haskell Libraries邮件列表上select更简单的实现：
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]
请记住，这3个是等价的（ second是来自Control.Arrow的函数）：
[(y,x:ys) | (y,ys) <- select xs]
map ((y,ys) -> (y,x:ys)) (select2 xs)
map (second (x:)) (select2 xs)
以下是如何使用select的示例：
select [1,2,3] -- [(1,[2,3]),(2,[1,3]),(3,[2,1])]
在我实现select之前，我试图在Hayoo中查找类型为[a] -> [(a, [a])]的函数，在各种库中有几个实现：
utility-ht包中removeEach HaskellForMaths包中picks hmt-diagrams包的parts' rosso包的extractEachElem extractElem从spaceprobe包 permutations
问题是，我们的select不足以产生所有排列。 我们可以使用具有类型(a, [a]) -> [a] uncurry (:)来对每个元组的两部分进行处理，但是我们只能得到一些排列，而不是全部：
map (uncurry (:)) (select [1,2,3]) -- [[1,2,3],[2,1,3],[3,2,1]]
很明显，为什么select [1,2,3]会创建一个列表[(1,[2,3]),(2,[1,3]),(3,[2,1])] ，但我们必须排列子列表，这也是每个元组的第二部分！ 换句话说，如果我们有(1, [2,3]) ，我们也必须加上(1, [3,2]) 。
查找列表的所有排列的完整代码如下：
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : map ((y,ys) -> (y,x:ys)) (select xs)
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = [cons s2 | s <- select2 xs, s2 <- subpermutations s]
where cons :: (a, [a]) -> [a]
cons = uncurry (:)
subpermutations :: (a, [a]) -> [(a, [a])]
subpermutations (x,xs) = map (e -> (x, e)) $ permutations xs
请注意，我们函数的排列顺序与Data.List.permutations不同。 我们的函数具有词典顺序，而Data.List.permutations没有：
permutations [1,2,3] -- [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
Data.List.permutations [1,2,3] -- [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
最后，如果我们进一步简化我们的permutations函数，我们得到在Rosetta代码中的实现：
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : map ((y,ys) -> (y,x:ys)) (select xs)
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = [ y:zs | (y,ys) <- select xs, zs <- permutations ys]
还要注意，使用基于插入方法的Rosetta Code的实现与Data.List.permutations具有相同（非词典）顺序。
笔记
FWIW， uhc-util软件包中有一个函数scc :: [(a, [a])] -> [[a]] ，它查找Graph的强连通组件。 元组的第一部分是一个顶点，第二部分是所有顶点，顶点的边缘是顶点。 IOW，图1 --> 2 --> 3变为[(1, [2]), (2, [3])] 。
scc [(1,[2,3,4]),(2,[1,3,4]),(3,[2,1,4]),(4,[3,2,1])] -- [[3,4], [1,2]]