如何在DrRacket中执行幂集？

Question

我正在使用DrRacket的简写列表语言，并想要递归地生成幂集，但无法弄清如何实现。目前我只有这么多：

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

需要任何帮助都可以。

- user3109171

---

http://rosettacode.org/wiki/Power_set#Racket - Robert Harvey

（需要 racket/list）（定义 powerset 组合） - Ben Greenman

Answer 1

什么是幂集？一个集合的子集！
一个空集是任何集合的子集，
因此空集的幂集不是空的。
它（唯一）的元素是一个空集：

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

对于非空集合，存在一种选择，
    对于每个集合的元素，是要
    还是不要包含在子集中，
    子集是幂集的成员。

    因此，在将第一个元素与更小的幂集组合时，
    我们包括两种选择，
    通过递归地应用相同的过程来处理输入的其余部分：

       (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`

“没有答案，只有选择。” 实际上，
            所做的选择，就是答案的构成部分。

- Will Ness

Answer 2

在Racket中，

#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))

- soegaard

Answer 3

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

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

- Óscar López

---

是的，那是我最初编写的实现（因为它比我最终发布的版本更直接，所以直觉上想到了它），但我不喜欢生成元素的顺序。（我知道，集合与排序有什么关系呢？）不过，还是给你点赞。 :-) - C. K. Young

Answer 4

这是我实现的幂集函数（虽然我只在标准的Racket语言中进行了测试，没有在Beginning Student中测试）：

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

感谢samth提醒我，在Racket中flatmap被称为append-map！

- C. K. Young

---

我喜欢这个解决方案，它比我发布的那个更简单，并且是一个展示append-map用法的好例子。不过我想知道，为什么它会更慢呢？ - Óscar López

Answer 5

你可以只使用副作用：

(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) '())

- JasperShih

---

在https://docs.racket-lang.org/htdp-langs/beginner-abbr.html#%28part._beginner-abbr-pre-defined%29中没有`set!`，但是[tag:recursive-backtracking]很好而且简单。 - Will Ness

它可以在DrRacket上运行。 - JasperShih

我正在使用带有列表缩写的起始语言，并且我已经点赞了。 :) - Will Ness

好的，谢谢您的纠正。我也已经为您点赞了。 - JasperShih