我正在使用DrRacket的带有列表缩写的起始语言,并希望递归地生成一个powerset,但不知道如何做到这一点。我目前有这么多
(define
(powerset aL)
(cond
[(empty? aL) (list)]
任何帮助都是好的。
功率集中有什么?集合的子集!空集是 任何 集的子集,因此的幂集为空集的不是为空。它的(唯一)元素是一个空集:
(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`
"没有答案,只有选择" 相反,所做的选择就是答案
在机架中,
#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))
这是另一个实现,经过几次测试,它似乎比Chris对更大列表的回答更快。使用标准Racket:进行测试
(define (powerset aL)
(if (empty? aL)
'(())
(let ((rst (powerset (rest aL))))
(append (map (lambda (x) (cons (first aL) x))
rst)
rst))))
以下是我的电源集实现(尽管我只使用标准Racket语言测试它,而不是初学者):
(define (powerset lst)
(if (null? lst)
'(())
(append-map (lambda (x)
(list x (cons (car lst) x)))
(powerset (cdr lst)))))
(感谢samth提醒我,平面图在Racket中被称为append-map
!)
您只需使用副作用:
(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) '())