How to resolve the algorithm Set consolidation step by step in the EchoLisp programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Set consolidation step by step in the EchoLisp programming language

Table of Contents

Problem Statement

Given two sets of items then if any item is common to any set then the result of applying consolidation to those sets is a set of sets whose contents is: Given N sets of items where N>2 then the result is the same as repeatedly replacing all combinations of two sets by their consolidation until no further consolidation between set pairs is possible. If N<2 then consolidation has no strict meaning and the input can be returned.

See also

Let's start with the solution:

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

Source code in the echolisp programming language

;; utility : make a set of sets from a list
(define (make-set* s)
		(or (when (list? s) (make-set (map make-set* s))) s))
		
;; union of all sets which intersect - O(n^2)
(define (make-big ss)
(make-set
	(for/list ((u ss))
	(for/fold (big u) ((v ss)) #:when (set-intersect? big v)  (set-union big v)))))
	
;; remove sets which are subset of another one - O(n^2)
(define (remove-small ss)
	(for/list ((keep ss))
	#:when (for/and ((v ss))  #:continue (set-equal? keep v) (not (set-subset? v keep)))
	keep))
	
(define (consolidate ss) (make-set (remove-small (make-big ss))))

(define S (make-set* ' ((h i k) ( a b) ( b c) (c d) ( f g h))))
    → { { a b } { b c } { c d } { f g h } { h i k } }

(consolidate S)
    → { { a b c d } { f g h i k } }


  

You may also check:How to resolve the algorithm Copy stdin to stdout step by step in the BCPL programming language
You may also check:How to resolve the algorithm Random numbers step by step in the Sather programming language
You may also check:How to resolve the algorithm Van der Corput sequence step by step in the jq programming language
You may also check:How to resolve the algorithm Stem-and-leaf plot step by step in the Go programming language
You may also check:How to resolve the algorithm Enforced immutability step by step in the C# programming language