scheme - 方案中的配对组合

Question

我正在尝试找到可以使用方案中的 N 对列表进行的各种组合。这是我到目前为止的位置：

(define (pair-combinations list-of-pairs)
  (if (null? list-of-pairs)
      nil
      (let ((first (caar list-of-pairs))
            (second (cadar list-of-pairs))
            (rest (pair-combinations (cdr list-of-pairs))))
        (append
            (list (cons first rest))
            (list (cons second rest))
        ))))

现在，我不确定逻辑是否正确，但我立即注意到的是括号的伸缩。例如：

(define p1 '( (1 2) (3 4) (5 6) ))
(pair-combinations p1)
((1 (3 (5) (6)) (4 (5) (6))) (2 (3 (5) (6)) (4 (5) (6))))

显然这是来自list (...append 调用中的重复，所以结果看起来像(list 1 (list 2 (list 3 .... 有没有办法在单个函数中执行上述操作？如果是这样，我哪里出错了，如何正确完成？

我希望得到的答案是：

((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))

也就是说，从 N 对中选择一个元素的可能方式。

标签： schemeracketsicp

Answer 1

这是思考这个问题的一种方法。如果输入为空列表，则结果为()。如果输入是包含单个列表的列表，则结果只是映射list到该列表的结果，即(combinations '((1 2 3)))--> ((1) (2) (3))。

否则，可以通过获取输入中的第一个列表并将该列表中的每个项目添加到输入中其余列表的所有组合来形成结果。也就是说，(combinations '((1 2) (3 4)))可以通过将 的每个元素添加(1 2)到 中的每个组合中来找到(combinations '((3 4)))，它们是((3) (4))。

用两个程序来表达这一点似乎很自然。首先，一个combinations程序：

(define (combinations xss)
  (cond ((null? xss) '())
        ((null? (cdr xss))
         (map list (car xss)))
        (else
         (prepend-each (car xss)
                       (combinations (cdr xss))))))

现在prepend-each需要一个程序：

(define (prepend-each xs yss)
  (apply append
         (map (lambda (x)
                (map (lambda (ys)
                       (cons x ys))
                     yss))
              xs)))

在这里，该过程prepend-each接受一个列表xs和一个列表列表，yss并返回将每个xin添加xs到列表 in的结果yss。内部映射将每个列表ys放入yss其中并在其上包含一个xfrom xs。由于内部映射产生一个列表列表，而外部映射然后产生一个列表列表的列表，append用于在返回之前加入结果。

combinations.rkt> (combinations '((1 2) (3 4) (5 6)))
'((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))

现在已经找到了一种可行的方法，可以将其转换为单个过程：

(define (combinations-2 xss)
  (cond ((null? xss) '())
        ((null? (cdr xss))
         (map list (car xss)))
        (else
         (apply append
                (map (lambda (x)
                       (map (lambda (ys)
                              (cons x ys))
                            (combinations-2 (cdr xss))))
                     (car xss))))))

但是，我不会那样做，因为两个程序中的第一个版本似乎更清楚。

prepend-each仅查看使用和不使用的结果可能会有所帮助append：

combinations.rkt> (prepend-each '(1 2) '((3 4) (5 6)))
'((1 3 4) (1 5 6) (2 3 4) (2 5 6))

不使用append：

(define (prepend-each-no-append xs yss)
  (map (lambda (x)
         (map (lambda (ys)
                (cons x ys))
              yss))
       xs))

combinations.rkt> (prepend-each-no-append '(1 2) '((3 4) (5 6)))
'(((1 3 4) (1 5 6)) ((2 3 4) (2 5 6)))

可以看出，1添加到每个列表中((3 4) (5 6))以创建列表列表，然后2添加到每个列表中((3 4) (5 6))以创建列表列表。这些结果包含在另一个列表中，因为1和2来自外部映射(1 2)。这就是为什么append用来加入结果的原因。

一些最终改进

请注意，prepend-each当为空时返回一个空列表yss，但是xs当包含一个空列表时，返回一个包含分布在尽可能多列表中的元素的yss列表：

combinations.rkt> (prepend-each '(1 2 3) '(()))
'((1) (2) (3))

combinations当输入包含单个列表时，这与我们想要的结果相同。我们可以修改combinations为有一个基本情况：当输入为 时'()，结果为(())。这将允许prepend-each完成之前由 完成的工作(map list (car xss))，从而combinations更加简洁；该prepend-each程序没有改变，但为了完整起见，我将其包括在下面：

(define (combinations xss)
  (if (null? xss) '(())
      (prepend-each (car xss)
                    (combinations (cdr xss)))))

(define (prepend-each xs yss)
  (apply append
         (map (lambda (x)
                (map (lambda (ys)
                       (cons x ys))
                     yss))
              xs)))

更简洁combinations之后，我可能会想继续把它写成一个过程，毕竟：

(define (combinations xss)
  (if (null? xss) '(())
      (apply append
             (map (lambda (x)
                    (map (lambda (ys)
                           (cons x ys))
                         (combinations (cdr xss))))
                  (car xss)))))