Я использую начальный язык со списками сокращений для DrRacket и хочу рекурсивно сделать powerset, но не могу понять, как это сделать. у меня сейчас столько
(define
(powerset aL)
(cond
[(empty? aL) (list)]
любая помощь была бы хороша.
Я использую начальный язык со списками сокращений для DrRacket и хочу рекурсивно сделать powerset, но не могу понять, как это сделать. у меня сейчас столько
(define
(powerset aL)
(cond
[(empty? aL) (list)]
любая помощь была бы хороша.
В Ракете,
#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))
Вот моя реализация набора мощности (хотя я тестировал ее только на стандартном языке Racket, а не на начинающем студенте):
(define (powerset lst)
(if (null? lst)
'(())
(append-map (lambda (x)
(list x (cons (car lst) x)))
(powerset (cdr lst)))))
(Спасибо samth за напоминание о том, что плоская карта называется append-map
в Racket!)
append-map
. Интересно, а почему медленнее?
- person Óscar López; 17.12.2013
Вот еще одна реализация, после нескольких тестов она оказалась быстрее, чем ответ Криса для больших списков. Он был протестирован с использованием стандартного Racket:
(define (powerset aL)
(if (empty? aL)
'(())
(let ((rst (powerset (rest aL))))
(append (map (lambda (x) (cons (first aL) x))
rst)
rst))))
Вы можете просто использовать побочный эффект:
(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) '())
(require racket/list) (define powerset combinations)
docs.racket-lang.org/reference/ - person Ben Greenman   schedule 11.01.2017