scheme - Scheme中使用递归的排列

Question

我发现下面这段代码在 Scheme 中进行了排列。我的意思是，如果我输入类似的参数 '(1 2 3) 它会给我:

((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

代码如下:

(define (remove x lst)
  (cond
    ((null? lst) '())
    ((= x (car lst))(remove x (cdr lst)))
    (else (cons (car lst) (remove x (cdr lst))))))

(define (permute lst)
  (cond
    ((= (length lst) 1)(list lst))
    (else (apply append(map(lambda (i) (map (lambda (j)(cons i j))
                                            (permute (remove i lst))))lst)))))

第一个函数 remove，看起来很简单，它只删除 x 表示的字符，即使它是否重复，通过将它与列表的开头进行比较并与它的其余部分进行递归调用。

我不太明白的部分是置换函数。据我所知， map 将一个函数应用于参数的每个元素(在本例中为列表)，并且 apply 只将一个函数一次完全应用于所有参数。那么这条线到底在做什么:

(apply append(map(lambda (i) (map (lambda (j)(cons i j))
                                                (permute (remove i lst))))lst)))))

对我来说，它似乎只是想创建一个包含两个元素的对:i 和 j，它们将成为一个元素排列的列表(如果我们假设一个列表只是一堆串联的对) .但是用 i 再次调用置换和删除的部分，那部分在做什么？它只是删除列表的头部以生成列表的子集，其中元素 i 对的头部是固定的，直到它用完元素？

有什么帮助吗？

谢谢

Answer 1

让我们从内到外把它分开。修复 lst 并将内部表达式应用于其元素之一。

> (define lst '(1 2 3))
> (define i 1)
> (permute (remove i lst))
((2 3) (3 2))

看起来不错:内部表达式删除一个元素并递归生成列表其余部分的排列。现在 map lambda 在这些排列上:

> (map (lambda (j) (cons i j)) (permute (remove i lst)))
((1 2 3) (1 3 2))

因此，内部 map 生成所有以某些 i 开头的排列，我们在此处将其设置为 1。

外部 map 确保通过将 lst 的所有元素视为第一个元素来生成所有排列。

> (map (lambda (i) (map (lambda (j) (cons i j))
>                       (permute (remove i lst))))
>      lst)
(((1 2 3) (1 3 2)) ((2 1 3) (2 3 1)) ((3 1 2) (3 2 1)))

但这会生成嵌套过多的列表。应用 append 将列表列表展平，

> (append '(1 2) '(3 4) '(5 6))
(1 2 3 4 5 6)
> (apply append '((1 2) (3 4) (5 6)))
(1 2 3 4 5 6)

所以我们得到了一个简单的排列列表。