scheme - 接受 X 并返回 #t/#f 的所有集合的函数

Question

所以我一直坐在这里思考如何做到这一点，我很困惑，我希望它像

(Return_Set 2)  returns=> ((#t, #t) (#t, #f) (#f, #t) (#f, #f))
(Return_Set 1)  returns=> ((#t) (#f))
(define (Return_Set N) 

我知道(/ (expt 2 N) 2)我需要把所有#t然后附加到：

(Return_Set N-1) 

并为#f 做同样的事情，但从那里开始。

Answer 1

这是一个想法：编写一个返回任意数量列表之间的笛卡尔积的过程（提示：您可以通过谷歌搜索找到该算法！）。然后您将能够轻松解决此问题，如下所示：

(return-set 1) ; is equivalent to (cartesian-product '(#t #f))
=> '((#t #f))

(return-set 2) ; is equivalent to (cartesian-product '(#t #f) '(#t #f))
=> '((#t #t) (#t #f) (#f #t) (#f #f))

(return-set 3) ; is equivalent to (cartesian-product '(#t #f) '(#t #f) '(#t #f))
=> '((#t #t #t) (#t #t #f) (#t #f #t) (#t #f #f)
     (#f #t #t) (#f #t #f) (#f #f #t) (#f #f #f))

为了使事情更容易，还编写一个过程来构建一个重复值n次的新列表。现在问题的解决方案可以很容易地表达如下：

(define (cartesian-product . lsts)
  <???>) ; ToDo

(define (repeat element n)
  <???>) ; ToDo

(define (return-set n)
  (apply cartesian-product
         (repeat '(#t #f) n)))

我可以帮助您完成上述过程，但首先让我们看看到目前为止您尝试了什么，我的意思是：真正努力工作的代码，在 Stack Overflow 中，不赞成用勺子喂给家庭作业的答案。

更新：

那好吧。@GoZoner 直接回答了 OP 的作业，所以现在保留我的回答没有多大意义。这是使用 Racket 的可能解决方案：

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

(define (repeat elt n)
  (build-list n (const elt)))

(define (return-set n)
  (apply cartesian-product
         (repeat '(#t #f) n)))

Answer 2

这样就完成了：

(define (return-set n)
  (define (cons-of x)
    (lambda (l) (cons x l)))
  (assert (positive? n))
  (if (= n 1)
      '((#t) (#f))
      (let ((n_1 (return-set (- n 1))))
        (append (map (cons-of #f) n_1)
                (map (cons-of #t) n_1)))))

认识到 N 的结果只是建立在 N-1 的结果之上的关键见解。