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

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，这里有一个可能的实现（在球拍作品）：

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

现在，如果你不使用的球拍，这里的大部分使用标准香草实施程序;它应该在任何Scheme解释定义了fold-right样的程序工作：

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