使用递归在Scheme中进行排列

我发现了以下一段代码，它在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表示的字符与列表的开头进行比较并与列表的其余部分递归调用来删除x表示的字符，即使它是否重复。

我不太明白的部分是排列函数。据我所知，map 将一个函数应用于参数的每个元素（在本例中是一个列表），而 apply 只是一次将一个函数完全应用于所有参数。那么这一行到底在做什么：

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

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

有什么帮助吗？

Thanks

让我们从内到外把它拆开。使固定lst并将内部表达式应用于其元素之一。

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

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

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

所以内在map产生以某些开头的所有排列i，我们设置为1 here.

外层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)

这样我们就得到了一个简单的排列列表。