How to resolve the algorithm Set step by step in the Scheme programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Set step by step in the Scheme programming language

Table of Contents

Problem Statement

A   set  is a collection of elements, without duplicates and without order.

Show each of these set operations:

As an option, show some other set operations. (If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.) As another option, show how to modify a mutable set.

One might implement a set using an associative array (with set elements as array keys and some dummy value as the values). One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators). The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.

Let's start with the solution:

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

Source code in the scheme programming language

(define (element? a lst)
  (and (not (null? lst))
       (or (eq? a (car lst))
	   (element? a (cdr lst)))))

; util, not strictly needed
(define (uniq lst)
  (if (null? lst) lst
    (let ((a (car lst)) (b (cdr lst)))
      (if (element? a b)
	(uniq b)
	(cons a (uniq b))))))

(define (intersection a b)
  (cond ((null? a) '())
	((null? b) '())
	(else
	  (append (intersection (cdr a) b)
		  (if (element? (car a) b)
		    (list (car a))
		    '())))))

(define (union a b)
  (if (null? a) b
    (union (cdr a)
	   (if (element? (car a) b)
	     b
	     (cons (car a) b)))))

(define (diff a b) ; a - b
  (if (null? a) '()
    (if (element? (car a) b)
      (diff (cdr a) b)
      (cons (car a) (diff (cdr a) b)))))

(define (subset? a b) ; A ⊆ B
  (if (null? a) #t
    (and (element? (car a) b)
	 (subset? (cdr a) b))))

(define (set-eq? a b)
  (and (subset? a b)
       (subset? b a)))


  

You may also check:How to resolve the algorithm Sorting algorithms/Stooge sort step by step in the Tcl programming language
You may also check:How to resolve the algorithm Program name step by step in the PowerBASIC programming language
You may also check:How to resolve the algorithm Integer sequence step by step in the Batch File programming language
You may also check:How to resolve the algorithm Permutations step by step in the Swift programming language
You may also check:How to resolve the algorithm Character codes step by step in the Tcl programming language