问题描述
是否可以使用球拍功能来返回给定列表的功率集??
约束-
- 没有显式递归
- 使用抽象列表功能
- 代码包含在两行中(实际要求)
例如:(powerset'(1 2))
'(((1 2)(1)(2)())
以任何顺序.
我发现的其他问题仍然使用显式递归.
The other question I found still uses explicit recursion.
我的工作流程:
- 以
(powerset'(a b c))
为例, - 首先获取不超过
(expt 2(length list))的整数列表;'(0 1 2 3 4 5 6 7)
- 将它们转换为各自的二进制形式
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))
- 将'(1 2 3)映射到二进制列表.例如:
2->'(0,1,0)->'(((0,a)(1,b)(0,c))
- 使用lambda过滤结果列表,以便我们将元素保留为1,例如
'((1,b))
. - 提取功率集
- Taking
(powerset '(a b c))
as an example, - First get a list of whole numbers up to
(expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
- Convert them into their respective binary form
2->(0,1,0)
. So we get'((0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1))
- map '(1 2 3) to the list of binaries. For eg:
2->'(0,1,0)->'((0,a) (1,b) (0,c))
- filter the resulting list with a lambda such that we keep elements with 1, like
'((1,b))
. - Extract the powerset
我的方法存在问题
它不遵循问题在1行中的约束(除了函数标头).
It does not follow constraint of the question being in 1 line (additional to function header).
(define (powerset list)
( ... )) ;; ie the code is contained in 2 lines of 80 characters
我在任务中有这个问题,是奖金问题,但我无法做到.
I had this question in my assignment as a bonus question but I wasn't able to do it.
- 什么是抽象列表函数?
-
foldl
,folder
和map
之类的功能 - Functions like
foldl
,foldr
andmap
- 我的奖金包括3个子部分
- 第1部分要求以我想要的任何方式简单地实现此功能.所以我使用了递归操作
- 第2部分是我询问的问题.这样做特别困难,因为在两行之内 附加了一些代码约束
- 第3部分应该是最难的.
但是,有趣的是,我研究了 Y-combinator
,并且能够解决这个问题(经过6个小时的编码).
However, funny thing, I studied Y-combinator
and was able to solve this one (after 6 hrs of coding).
推荐答案
要回答第2部分的奖金,
To answer your bonus part 2:
(define (pws l)
(foldr (lambda (e a) (append (map (lambda (x) (cons e x)) a) a)) '(()) l))
两行,每行少于80个字符,第一行保留用于 define
(因此,一个行).
Two lines, less than 80 chars each, first line reserved for the define
(so, one line).
如果不允许使用 append
,那么我们也将 append ... map
组合也转换为 folder
:
If append
isn't allowed, then we turn the append ... map
combination into a foldr
as well:
(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个字符).
(with precisely 80 chars in its second line).
另一种编码方法是来自 this的基于 append-map
的代码(第二段).答案,仅当使用 folder
重新编码时,该答案就会变成
Another way to code this is the append-map
-based code (the second snippet) from this answer which, when re-coded with foldr
only, becomes
(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))
可能无法完全满足您的要求.
which might or might not fulfill your requirements exactly.
这篇关于使用抽象列表功能的列表功率集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!