怎么在DrRacket做一个powerset？

4 回答

• 3

  What's in a powerset? A set's subsets. 
              An empty set is any set's subset,
              so powerset of empty set's not empty. 
              Its only element it is an empty set:
  

  (define
    (powerset aL)
    (cond
      [(empty? aL) (list empty)]
      [else
  

  As for non-empty sets, there is a choice,
              for each set's element, whether to be
              or not to be included in subset
              which is a member of a powerset. 
              We thus proceed along the input list, combining 
              each element with a resulting set, 
              that, which we get recursively applying 
              our procedure to the rest of input:
  

  (add-into (powerset (rest aL))
                   (first aL))]))
  
  (define
    (add-into r a)                  ; `r` is recursive result, `a` is first element
    (cond
      [(empty? r)  empty]           ; nothing to add `a` to
      [else
        (cons (cons a (first r))    ; either add `a`,
              (cons (first r)       ;   or not, to the first in `r`
                    (add-into       ; and recursively proceed
                        (rest r)    ;   to add `a` into the rest of `r`
                        a )))]))
  

  "There are no answers, only choices". Rather, 
              the choices made, are what the answer's made of.
  

  回复于 2024-05-15T22:34:37+08:00
• 3

  这是我的电源设置实现（虽然我只使用标准的Racket语言测试它，而不是初学者）：

  (define (powerset lst)
    (if (null? lst)
        '(())
        (append-map (lambda (x)
                      (list x (cons (car lst) x)))
                    (powerset (cdr lst)))))
  

  （感谢samth提醒我在Racket中将flatmap称为 append-map ！）

  回复于 2024-05-15T22:34:37+08:00
• 7

  这是另一个实现，经过几次测试后，它似乎比Chris对更大的列表的回答更快 . 它使用标准球拍测试：

  (define (powerset aL)
    (if (empty? aL)
        '(())
        (let ((rst (powerset (rest aL))))
          (append (map (lambda (x) (cons (first aL) x))
                       rst)
                  rst))))
  

  回复于 2024-05-15T22:34:37+08:00
• 3

  在球拍中，

  #lang racket
  
  (define (power-set xs)
    (cond
      [(empty? xs) (list empty)]                 ; the empty set has only empty as subset
      [(cons? xs)  (define x  (first xs))        ; a constructed list has a first element
                   (define ys (rest  xs))        ; and a list of the remaining elements
                   ;; There are two types of subsets of xs, thouse that
                   ;; contain x and those without x.
                   (define with-out-x            ; the power sets without x
                     (power-set ys))                 
                   (define with-x                ; to get the power sets with x we 
                     (cons-all x with-out-x))    ; we add x to the power sets without x
                   (append with-out-x with-x)])) ; Now both kind of subsets are returned.
  
  (define (cons-all x xss)
    ; xss is a list of lists
    ; cons x onto all the lists in xss
    (cond
      [(empty? xss) empty]
      [(cons?  xss) (cons (cons     x (first xss))    ; cons x to the first sublist
                          (cons-all x (rest xss)))])) ; and to the rest of the sublists
  

  去测试：

  (power-set '(a b c))
  

  回复于 2024-05-15T22:34:37+08:00