2

我正在尝试实现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 [] = [[]]
4

2 回答 2

4

你的循环不一样。

i <- [len,len-1..0]

对比

for i in xrange(len(A)-1,-1,-1):

第一种情况，您绑定i到长度，而不是长度减一。结果是delete i xs返回xs，所以你得到无限递归。

我还有一些旁注。

首先!!是线性时间。您最好编写一个辅助函数，将 that !!、 thedelete和对输入的迭代组合到一个列表遍历中。类似的东西select :: [a] -> [(a, [a])]。你可以有效地做到这一点。

其次，++也是线性时间。使用它将单个元素附加到现有列表很慢。如果您的目标只是产生所有排列，而不是它们的特定顺序，您可能应该使用(xs !! i) : ys作为返回的表达式。（针对针对第一点所做的任何更改进行了适当修改。）

于 2013-06-06T16:06:49.467 回答
1

select

根据@Carl 的回答，我实现了select :: [a] -> [(a, [a])]功能。它的任务是生成一个 tuples 列表(a, [a])，其中 tuple 的第一部分是列表中的一个元素，而 tuple 的第二部分是列表中除该元素之外的所有元素。

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

但是，我select在Haskell Libraries 邮件列表中发现了更简单的实现：

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])]

在我实现之前，我尝试在Hayooselect中找到具有类型的函数，各种库中有几种实现：[a] -> [(a, [a])]

permutations

问题是，我们select还不足以生成所有排列。uncurry (:)我们可以使用具有类型的 对每个元组的两个部分进行 cons (a, [a]) -> [a]，但我们只能得到一些排列，而不是全部：

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 Code中的实现：

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，有一个scc :: [(a, [a])] -> [[a]]来自 package的函数uhc-util，它可以找到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]]
于 2015-08-23T21:32:45.880 回答