list - 从列表中生成方案中的所有可能性

Question

我有一个子列表列表:

((a b c) (e f) (z h)) 

我想生成这样的东西:

((a e z) (a f z) (a e h) (a f h) (b e z) (b e h) ... ) and so on.

我想在给定一个子列表列表的情况下生成所有可能的子列表，这些子列表包含来自每个输入子列表的元素。

我怎样才能得到这个输出？

Answer 1

您描述的是 cartesian product列表的列表，这是一个可能的实现(在 Racket 中工作):

(define (cartesian-product lsts)
  (foldr (lambda (lst acc)
           (for*/list ((x (in-list lst))
                       (y (in-list acc)))
             (cons x y)))
         '(())
         lsts))

现在，如果您不使用 Racket，这里有一个主要使用标准程序的普通实现；它应该适用于定义类似 fold-right 过程的任何 Scheme 解释器:

(define (flatmap f lst)
  (apply append (map f lst)))

(define (cartesian-product lsts)
  (foldr (lambda (lst acc)
           (flatmap (lambda (x)
                      (map (lambda (y)
                             (cons x y))
                           acc))
                    lst))
         '(())
         lsts))

无论哪种方式，它都按预期工作:

(cartesian-product '((a b c) (e f) (z h)))

=> '((a e z) (a e h) (a f z) (a f h) (b e z) (b e h)
     (b f z) (b f h) (c e z) (c e h) (c f z) (c f h))