lisp - (方案)递归函数来计算某些列表的所有可能组合？

Question

计算所有可能的列表组合的递归函数示例是什么？例如，(combine (list 1 2 3) (list 1 2)) 应该返回 '((1 1) (1 2) (2 1) (2 2) (3 1 ) (3 2))。

Answer 1

这是我的看法；我首先定义了一个助手 concat/map，它接受一个列表和一个函数。与常规 map 一样，它将该函数应用于列表中的每个元素。不过，与 map 不同的是，它使用 append 来合并结果，而不是 cons。这很有用，因为我们想要返回单层列表作为答案:

(define concat/map
  (lambda (ls f)
    (cond
      [(null? ls) '()]
      [else (append (f (car ls)) (concat/map (cdr ls) f))])))

然后，为两个列表编写 combine 就很简单了。您获取第一个列表的每个元素，然后将每个列表与第二个列表中的元素 x 组合起来。由于这会返回第一个列表中每个元素的答案列表，请使用 concat/map 将其按我们的需要放在一起:

(define combine
  (lambda (xs ys)
    (concat/map xs (lambda (x)
                     (map (lambda (y) (list x y)) ys)))))

对一个或多个列表进行操作的 combine 版本，我们称之为 combine*，有点棘手。不是让所有列表都将 x 与第二个列表中的元素相结合，我们只是递归地要求所有剩余 ys 的乘积，然后是 cons x 到每个结果上。当只有两个列表要组合时递归停止，并在这种情况下使用原始的 combine。

(define combine*
  (lambda (xs . ys*)
    (cond
      [(null? ys*) (map list xs)]
      [(null? (cdr ys*)) (combine xs (car ys*))]
      [else (concat/map xs (lambda (x)
                             (map (lambda (y) (cons x y))
                                  (apply combine* ys*))))])))

作为奖励，这种使用 concat/map 做一些工作并组合结果答案的模式实际上是 list monad .这里简化了，但是结构很到位。