7

我正在使用带有 DrRacket 列表缩写的起始语言，并且想要递归地创建一个 powerset，但无法弄清楚如何去做。我目前有这么多

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

任何帮助都会很好。

4

5 回答 5

14 
            电源组中有什么？一个集合的子集！
            空集是任何集合的子集，
            所以空集的幂集不是空的。
            它的（唯一）元素是一个空集：
(define
  (powerset aL)
  (cond
    [(empty? aL) (list empty)]
    [else

            至于非空集，有一个选择，
            对于每个集合的元素，是否为
            或不包含在子集中
            它是powerset的成员。

            因此，我们在组合时包括了这两种选择
            第一个具有较小幂集的元素，
            那，我们递归地应用
            其余输入的过程相同：
       (combine (first aL)
                (powerset (rest aL)))]))

(define
  (combine a r)                      ; `r` for Recursive Result
  (cond
    [(empty? r)  empty]              ; nothing to combine `a` with
    [else
      (cons (cons a (first r))       ; Both add `a` and
          (cons (first r)            ;   don't add, to first subset in `r`
              (combine               ; and do the same
                    a                ;   with 
                    (rest r))))]))   ;   the rest of `r`

            “没有答案，只有选择”。相反， 
            做出的选择就是答案的组成部分。
于 2013-12-17T00:05:00.587 回答
4

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

(define (powerset aL)
  (if (empty? aL)
      '(())
      (let ((rst (powerset (rest aL))))
        (append (map (lambda (x) (cons (first aL) x))
                     rst)
                rst))))
于 2013-12-17T01:14:35.543 回答
4

在球拍中，

#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))
于 2017-10-25T21:01:07.273 回答
3

这是我的 power set 实现（尽管我只使用标准 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！）

于 2013-12-17T00:04:50.087 回答
1

你可以只使用副作用：

(define res '())

(define
  (pow raw leaf)
  (cond
    [(empty? raw) (set! res (cons leaf res))
                  res]
    [else (pow (cdr raw) leaf)
          (pow (cdr raw) (cons (car raw) leaf))]))

(pow '(1 2 3) '())
于 2020-05-14T03:19:50.990 回答