Как сделать powerset в DrRacket?

Question

Я использую начальный язык со списком сокращений для DrRacket и хочу рекурсивно сделать powerset, но не могу понять, как это сделать. У меня сейчас так много

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

любая помощь будет хорошей.

Answer 1

 Что в powerset? Подмножества набора.  
             Пустой набор является подмножеством любого набора, 
             так что powerset пустого набора не пуст.  
             Единственный его элемент - это пустой набор: 

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

 Что касается непустых множеств, есть выбор, 
             для каждого элемента набора, будь то 
             или не быть включенным в подмножество 
             который является членом powerset. 

             Таким образом, мы продвигаемся по списку ввода, объединяя  
             каждый элемент с результирующим набором,  
             то, что мы получаем рекурсивно  
             наша процедура для остальной части ввода: 

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

 "Там нет ответов, только выбор". Скорее,  
             сделанный выбор - вот из чего сделан ответ. 

Answer 2

В ракетке,

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

Answer 3

Вот еще одна реализация, после нескольких тестов она кажется быстрее, чем ответ Криса для больших списков. Он был протестирован с использованием стандартной ракетки:

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

Answer 4

Вот моя реализация набора мощности (хотя я тестировал его только на стандартном языке Racket, а не на Beginning Student):

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

(Спасибо Sam Tobin-Hochstadt за напоминание, что flatmap называется append-map в ракетку!)

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