使用抽象列表函数的列表的Powerset

Question

是否可以制作一个球拍函数来返回给定列表的幂集？

---

约束-

1. 无显式递归
2. 使用抽象列表函数
3. 包含在2行中的代码(实际要求(

---

例如：(powerset '(1 2))

'((1 2) (1) (2) ())

以任何顺序。

我发现的另一个问题仍然使用显式递归。

---

我的工作流程：

1. 以CCD_ 3为例
2. 首先获取一个到(expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)的整数列表
3. 将它们转换为各自的二进制形式2->(0,1,0)。所以我们得到'((0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1))
4. 将"(1 2 3(映射到二进制文件列表。例如：2->'(0,1,0)->'((0,a) (1,b) (0,c))
5. 用lambda过滤得到的列表，这样我们就可以保持元素为1，比如'((1,b))
6. 提取电源

---

我的方法存在问题

它不遵循问题在一行中的约束(函数标题的附加部分(。

(define (powerset list)
( ... )) ;; ie the code is contained in 2 lines of 80 characters

---

我在作业中有这个问题作为奖励问题，但我没能做到。

1. 什么是抽象列表函数

• 类似foldl、foldr和map的函数

2. 我的奖金包括3个子部分

• 第1部分要求以我想要的任何方式简单地制作这个函数。所以我用递归来做
• 第2部分是我提出问题的部分。这一次特别困难，因为添加了代码的约束，使其在2行内
• 第三部分应该是最艰难的

不要编写任何辅助函数，并且不要使用任何显式递归(即，函数不能按名称调用自身(。不要使用任何抽象列表函数。实际上，只使用以下Racket函数、常量和特殊形式的列表：cons、first、rest、empty?、empty、lambda和cond

然而，有趣的是，我研究了Y-combinator，并能够解决这个问题(经过6小时的编码(。

Answer 1

回答您的奖金第2部分：

(define (pws l) 
(foldr (lambda (e a) (append (map (lambda (x) (cons e x)) a) a)) '(()) l))

两行，每行少于80个字符，第一行保留给define(因此，一行(。

如果不允许append，那么我们也将append ... map组合转换为foldr：

(define (pws-fr l) 
(foldr (lambda (e a)
(foldr (lambda (x r)
(cons (cons e x) r))
a a))
'(()) l))

或简称

(define (pws-fr-1 l) 
(foldr (lambda (e a) (foldr (lambda (x r) (cons (cons e x) r)) a a)) '(()) l))

(第二行正好有80个字符(。

另一种编码方式是基于append-map的代码(第二个片段(，当仅使用foldr重新编码时，它将变为

(define (pws-am-fr l) 
(foldr (lambda (e a)
(foldr (lambda (x r)
(cons x (cons (cons e x) r)))
'() a))
'(()) l))

或缩短

(define (pws-am-fr1 l) (foldr (lambda (e a)
(foldr (lambda (x r) (cons x (cons (cons e x) r))) '() a)) '(()) l))

这可能会也可能不会完全满足您的要求。