Haskell中的置换算法

Question

我在Haskell教科书中阅读了此置换函数示例，我想知道是否有人可以帮助我了解正在发生的事情。另外，假设函数delete只是从列表中删除第一次出现的值并返回列表

perms [] = [[]]
perms p = [x:xs | x <-p, xs <- perms (delete x p)]

我知道空列表等于空列表。在所有其他情况下，列表的开头都以x开头，除开头以外的数字都通过算法递归。

我的问题是这是如何工作的，例如，我对伪代码的理解是

perms[1,2,3]
x <- 1
xs <- [2,3]
perms [2,3]
x <- 2
xs <- 3
perms [3]
x <- 3
xs <- []

这将产生列表[1,2,3]，该算法如何产生其他列表结果。

该代码的输出如下：

>perms [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 

Answer 1

表达方式：

[x:xs | x <- p, xs <- perms (delete x p)]

是一个列表推导，这意味着a <- b右侧的每个表达式都形成了一种隐式循环，您的伪代码无法解释这种隐式循环。

用带有显式循环的伪代码编写，等效于：

for each x in p:
  for each xs in perms (delete x p):
    yield (x:xs)
-- and return the list of all results yielded

然后从下至上地对定义进行递归思考可能会有所帮助。如果perm [n]为any 运行n，则仅对进行外部循环评估x = n，因为：

perms (delete n [n]) = perms [] = [[]]

内部循环等效于：

for each xs in [[]]
  ...

并且仅针对进行评估xs = []。因此，仅产生一个值：

x:xs = n:[] = [n]

因此，换句话说，perm [n]给出了单个元素的列表。[n][[n]]

如果继续前进perm [1,2]并想象展开循环：

-- for each x in [1,2]
first, for x = 1
  -- for each xs in perms (delete 1 [1,2]) = perms [2] = [[2]]
  so only for xs = [2]
    yield (x:xs) = yield (1:[2]) = yield [1,2]
second, for x = 2
  -- for each xs in perms (delete 2 [1,2]) = perms [1] = [[1]]
  so only for xs = [1]
    yield (x:xs) = yield (2:[1]) = yield [2,1]

因此产生两个值，即[1,2]和[2,1]，给出：

perm [1,2] = [[1,2],[2,1]]

这显然可以推广到任何一个perm [a,b] = [[a,b],[b,a]]，因此我们可以最终计算出perm [1,2,3]：

-- for each x in [1,2,3]
first, for x = 1
  -- for each xs in perms (delete 1 [1,2,3]) = perms [2,3] = [[2,3],[3,2]]
  first for xs = [2,3]
    yield (x:xs) = yield (1:[2,3]) = yield [1,2,3]
  second for xs = [3,2]
    yield (x:xs) = yield [1,3,2]
second, for x = 2
  -- for each xs in perms (delete 2 [1,2,3]) = [[1,3],[3,1]]
  first for xs = [1,3]
    yield (x:xs) = yield [2,1,3]
  second for xs = [3,1]
    yield (x:xs) = yield [2,3,1]
third, for x = 3
  first for xs = [1,2]
    yield [3,1,2]
  second for xs = [2,1]
    yield [3,2,1]

总共产生了六个值，列出了：

perms [1,2,3] = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]