How to resolve the algorithm Power set step by step in the Scheme programming language

Published on 12 May 2024 09:40 PM
#Scheme

How to resolve the algorithm Power set step by step in the Scheme programming language

Table of Contents

Problem Statement

A   set   is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored. Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.

By using a library or built-in set type, or by defining a set type with necessary operations, write a function with a set S as input that yields the power set 2S of S.

For example, the power set of     {1,2,3,4}     is For a set which contains n elements, the corresponding power set has 2n elements, including the edge cases of empty set. The power set of the empty set is the set which contains itself (20 = 1): And the power set of the set which contains only the empty set, has two subsets, the empty set and the set which contains the empty set (21 = 2):

Extra credit: Demonstrate that your language supports these last two powersets.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Power set step by step in the Scheme programming language

Source code in the scheme programming language

(define (power-set set)
  (if (null? set)
      '(())
      (let ((rest (power-set (cdr set))))
        (append (map (lambda (element) (cons (car set) element))
                     rest)
                rest))))

(display (power-set (list 1 2 3)))
(newline)

(display (power-set (list "A" "C" "E")))
(newline)

(define (power-set lst)
  (define (iter yield)
    (let recur ((a '()) (b lst))
      (if (null? b) (set! yield
		      (call-with-current-continuation
			(lambda (resume)
			  (set! iter resume)
			  (yield a))))
	(begin (recur (append a (list (car b))) (cdr b))
	       (recur a (cdr b)))))

    ;; signal end of generation
    (yield 'end-of-seq))

  (lambda () (call-with-current-continuation iter)))

(define x (power-set '(1 2 3)))
(let loop ((a (x)))
  (if (eq? a 'end-of-seq) #f
    (begin
      (display a)
      (newline)
      (loop (x)))))

(define (power_set_iter set)
  (let loop ((res '(())) (s set))
    (if (empty? s)
        res
        (loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))

You may also check:How to resolve the algorithm Integer sequence step by step in the 11l programming language
You may also check:How to resolve the algorithm Rock-paper-scissors step by step in the Mercury programming language
You may also check:How to resolve the algorithm Metronome step by step in the Java programming language
You may also check:How to resolve the algorithm Read entire file step by step in the Inform 7 programming language
You may also check:How to resolve the algorithm Successive prime differences step by step in the Julia programming language