How to resolve the algorithm Set step by step in the Scheme programming language
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