Union of set of ranges in Scheme -
i need write scheme function (union s1 s2)
when given 2 sets, let's
s1 = ((1 3) (5 13) (25 100)) s2 = ((2 4) (17 26) (97 100))
will give
(union s1 s2) ----> ((1 4) (5 13) (17 100))
also if
s1 = ((1 3) (5 13) (25 110) (199 300)) s2 = ((2 4) (17 26) (97 100) (110 200) (288 500))
then
(union s1 s2) ----> ((1 4) (5 13) (17 500))
can suggest me how this? have no idea how start.
instead of working 2 sets, suggest
- merging 2 sets 1 combined list (ordered on
car
) - making second pass merge elements, maintaining accumulator list (result, in reversed order).
that way, compare first , second element of input (merged) list, , know ordered, simplifies code:
- empty merged list => return result
- one element left => push element onto result, , return result, reversed back
- at least 2 elements in list
- if 2 elements don't overlap, push first element onto result, , loop on rest of merged list,
- otherwise replace 2 elements merged element, loop
example execution (your 2nd):
(union '((1 3) (5 13) (25 110) (199 300)) '((2 4) (17 26) (97 100) (110 200) (288 500))) lst: ((1 3) (2 4) (5 13) (17 26) (25 110) (97 100) (110 200) (199 300) (288 500)) res: () lst: ((1 4) (5 13) (17 26) (25 110) (97 100) (110 200) (199 300) (288 500)) res: () lst: ((5 13) (17 26) (25 110) (97 100) (110 200) (199 300) (288 500)) res: ((1 4)) lst: ((17 26) (25 110) (97 100) (110 200) (199 300) (288 500)) res: ((5 13) (1 4)) lst: ((17 110) (97 100) (110 200) (199 300) (288 500)) res: ((5 13) (1 4)) lst: ((17 110) (110 200) (199 300) (288 500)) res: ((5 13) (1 4)) lst: ((17 200) (199 300) (288 500)) res: ((5 13) (1 4)) lst: ((17 300) (288 500)) res: ((5 13) (1 4)) lst: ((17 500)) res: ((5 13) (1 4)) lst: () res: ((17 500) (5 13) (1 4)) final result: ((1 4) (5 13) (17 500))
i wrote code, it's 11 lines long , quite simple if follow approach.
edit
since ask code, here's initial version wrote:
(define (union set1 set2) (let loop ([lst (sort (append set1 set2) < #:key car)] [res null]) (if (null? lst) (reverse res) (let ([e1 (car lst)] [cd (cdr lst)]) (if (null? cd) (loop null (cons e1 res)) (let ([e2 (car cd)] [e1y (cadr e1)]) (if (> (car e2) e1y) (loop cd (cons e1 res)) (loop (cons (list (car e1) (max e1y (cadr e2))) (cdr cd)) res))))))))
optionally, if want/need avoid append
, sort
, have own merge
procedure so:
(define (merge lst1 lst2 cmp key) (let loop ((lst1 lst1) (lst2 lst2) (res null)) (cond ((and (null? lst1) (null? lst2)) (reverse res)) ((and (not (null? lst1)) (or (null? lst2) (cmp (key lst1) (key lst2)))) (loop (cdr lst1) lst2 (cons (car lst1) res))) (else (loop lst1 (cdr lst2) (cons (car lst2) res))))))
and replace second line of union
procedure with
(let loop ([lst (merge set1 set2 < caar)] [res null])
hope helps.
Comments
Post a Comment