本文介绍了使用抽象列表功能的列表功率集的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

约束-

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


例如:(powerset'(1 2))

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

以任何顺序.

我发现的其他问题仍然使用显式递归.

The other question I found still uses explicit recursion.

我的工作流程:

  1. (powerset'(a b c))为例,
  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. 提取功率集
  1. Taking (powerset '(a b c)) as an example,
  2. First get a list of whole numbers up to (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
  3. 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))
  4. map '(1 2 3) to the list of binaries. For eg: 2->'(0,1,0)->'((0,a) (1,b) (0,c))
  5. filter the resulting list with a lambda such that we keep elements with 1, like '((1,b)).
  6. 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.

  1. 什么是抽象列表函数?

  • foldl folder map
  • 之类的功能

    • Functions like foldl, foldr and map
      1. 我的奖金包括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.

        这篇关于使用抽象列表功能的列表功率集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-17 19:19
查看更多