scheme - 置换方案代码的解释

Question

这是一个生成元素列表排列的方案代码：

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

如果我们将代码分开，我确实理解代码的每一部分，但我无法理解的是这一切如何导致生成排列？

假设我们获取列表‘(a b)，它是如何生成‘(a b)的‘(b a)？

我们首先a从列表中删除并b保留，但是您现在必须反对a的地方写在哪里b？b是单个元素，但在我对代码的解释中，b也将被删除，什么都没有了……</p>

标签： schemepermutationdefinition

Answer 1

(TL;DR: the verbal explanation is at the very end of this answer.)

Let's try following the definitions with let*-rewrites. The definitions are

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

We try

(permute '(a b))
≡
(let* ((lst '(a b)))
  (apply append
     (map (lambda (i)
             (map (lambda (j) (cons i j))
                  (permute (remove i lst))))
          lst)))
≡
(let* ((lst '(a b))
       (r  (map (lambda (i)
                  (map (lambda (j) (cons i j))
                       (permute (remove i lst))))
                lst)))
  (apply append r))
≡
(let* ((lst '(a b))
       (i1 'a)
       (r1 (map (lambda (j) (cons i1 j))
                       (permute (remove i1 lst))))
       (i2 'b)
       (r2 (map (lambda (j) (cons i2 j))
                       (permute (remove i2 lst))))
       (r (list r1 r2)))
  (apply append r))
≡
(let* ((lst '(a b))
       (i1 'a)
       (t1 (permute (remove i1 lst)))
       (r1 (map (lambda (j) (cons i1 j)) t1))
       (i2 'b)
       (t2 (permute (remove i2 lst)))
       (r2 (map (lambda (j) (cons i2 j)) t2))
       (r (list r1 r2)))
  (apply append r))
≡
(let* ((i1 'a)
       (t1 (permute '(b)))
       (r1 (map (lambda (j) (cons i1 j)) t1))
       (i2 'b)
       (t2 (permute '(a)))
       (r2 (map (lambda (j) (cons i2 j)) t2))
       (r (list r1 r2)))
  (apply append r))
≡
(let* ((i1 'a)
       (t1 '( (b) ))
       (r1 (map (lambda (j) (cons i1 j)) t1))
       (i2 'b)
       (t2 '( (a) ))
       (r2 (map (lambda (j) (cons i2 j)) t2))
       (r (list r1 r2)))
  (apply append r))

and so we get

(let* ((r1 (map (lambda (j) (cons 'a j)) '( (b) )))
       (r2 (map (lambda (j) (cons 'b j)) '( (a) )))
       (r (list r1 r2)))
  (apply append r))
≡
(let* ((r1 (list (cons 'a '(b))))
       (r2 (list (cons 'b '(a))))
       (r (list r1 r2)))
  (apply append r))
≡
(let* ((r1 (list '(a b)))
       (r2 (list '(b a)))
       (r (list r1 r2)))
  (apply append r))
≡
(let* ((r1  '((a b)))
       (r2  '((b a)))
       (r (list r1 r2)))
  (apply append r))
≡
(apply append (list '((a b)) '((b a))))
≡
(      append       '((a b)) '((b a)) )
≡
'(                    (a b)    (b a)  )

Follow the same technique if you need to convince yourself in the validity of the intermediate results.

---

In hindsight, we could simplify it a bit more aggressively, like

(let* ((lst '(a b))
       (i1 'a)
       (r1 (map (lambda (j) (cons i1 j))
                       (permute (remove i1 lst))))
       (i2 'b)
       (r2 (map (lambda (j) (cons i2 j))
                       (permute (remove i2 lst))))
       (r (list r1 r2)))
  (apply append r))
≡
(let* ((lst '(a b))
       (i1 'a)
       (t1 (permute (remove i1 lst)))
       (r1 (map (lambda (j) (cons i1 j)) t1))
       (i2 'b)
       (t2 (permute (remove i2 lst)))
       (r2 (map (lambda (j) (cons i2 j)) t2)))
  (apply append (list r1 r2)))
≡
(let* ((t1 (permute '(b)))
       (r1 (map (lambda (j) (cons 'a j)) t1))
       (t2 (permute '(a)))
       (r2 (map (lambda (j) (cons 'b j)) t2)))
  (append r1 r2))
≡
(let* ((r1 (map (lambda (j) (cons 'a j)) '( (b) )))
       (r2 (map (lambda (j) (cons 'b j)) '( (a) )))
       )
  (append r1        ; one row for each elt            '( a
          r2        ;  of the input list,                b
          ))        ;  spliced in place by append        )

etc., in the end revealing the structure of the computation in the more visually apparent manner:

• for each element of the input list,
  • find all the permutations of the remainder,
  • prepend that element to each of them,
• and join together the results from thus processing each element in the input list, by appending all those results together.

(thus justifying my other, pseudocode-based answer here).