计算所有可能的列表组合的递归函数的例子是什么?例如,(combine (list 1 2 3) (list 1 2))
应该返回'((1 1) (1 2) (2 1) (2 2) (3 1) (3 2))
.
问问题
3555 次
2 回答
4
这是我的看法;我首先定义了一个 helper 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。这里简化了,但结构已经到位。
于 2011-04-05T04:24:05.410 回答
3
这是我的解决方案。要求 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)))
于 2011-04-05T03:30:31.453 回答