使用抽象列表功能的列表功率集

问题描述：

是否可以使用球拍功能来返回给定列表的功率集??

约束-

没有显式递归
使用抽象列表功能
代码包含在两行中(实际要求)

例如:(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 and map

我的奖金包括3个子部分

第1部分要求以我想要的任何方式简单地实现此功能.所以我使用了递归操作
第2部分是我询问的问题.这样做特别困难，因为在两行之内
第3部分应该是最难的.

请勿编写任何辅助函数，并且不使用任何显式递归(即，您的函数无法按名称自行调用).不要使用任何抽象列表函数.实际上，仅使用以下Racket函数，常量和特殊形式的列表: cons ， first ， rest ， empty?， empty ， lambda 和 cond .

Do not write any helper functions, and do not use any explicit recursion (i.e., your function cannot call itself by name). Do not use any abstract list functions. In fact, use only the following list of Racket functions, constants and special forms: cons, first, rest, empty?, empty, lambda, and cond.

但是，有趣的是，我研究了 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.

使用抽象列表功能的列表功率集

相关推荐