(方案)递归函数，用于计算某些列表的所有可能组合

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 做一些工作并组合结果答案的模式实际上是列表 monad。这里简化了，但结构已经到位。

Answer 2

这是我的解决方案。要求 SRFI 1 和 26 可用。

(define (cartesian-product first . rest)
  (define (iter l result)
    (define (prepend-all x)
      (map (cut cons <> x) l))
    (concatenate (map prepend-all result)))
  (map reverse (fold iter (map list first) rest)))