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

  1. merging 2 sets 1 combined list (ordered on car)
  2. 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

Popular posts from this blog

Android layout hidden on keyboard show -

i have strange problem layout. when tap on edittext , keyboard shown edittext stay on bottom , when tap on to hide keyboard , keyboard hides , edittext go should when want input text. when tap again, keyboard shown , edittext goes down behind keyboard... <relativelayout android:layout_width="match_parent" android:layout_height="match_parent" > <scrollview android:layout_width="match_parent" android:layout_height="fill_parent" android:above="@+id/rl_commands"> <textview android:layout_width="match_parent" android:layout_height="wrap_content"/> </scrollview> <relativelayout android:layout_width="match_parent android:layout_height="24dp" android:id="@+id/rl_commands" android:alignparentbottom="true">
Read more

google app engine - 403 Forbidden POST - Flask WTForms -

i have flask application running on google app engine. trying submit form built using wtform , keep getting following error. 403 forbidden: don't have permission access requested resource. either read-protected or not readable server. location.html (part of code) <form method=post action="/home/location"> .... <button type="submit" class="btn btn-primary" value="submit"> directions </button> </form> main.py @app.route('/home/location', methods=['post', 'get']) def location(): form = cfcdirections.direction(request.form) print(request.method) if request.method == 'post' , form.validate(): print("after if") directions = cfcdirections() street_no = directions.no street = directions.street suburb = directions.suburb postcode = directions.postcode
Read more

c - Why would PK11_GenerateRandom() return an error -8023? -

i looking through internet trying find source of pk11_generaterandom() function see why function fail. have program uses function when moved new flavor of linux, fails after forking ( fork() ) since not believe there problem nss, suspect doing incorrectly disregarded in older versions of linux new 1 there issue. the openssl package same on 'good' , 'bad' server: openssl 0.9.8e-fips-rhel5 01 jul nss rpm differs though. 'good' has nss-3.12.2.0-2.el5 and bas has version nss-3.15.3-4.el5_10 the 'good' server uses quite obsolete linux: linux 2.6.18-128.el5 #1 smp wed jan 21 08:45:05 est 2009 x86_64 x86_64 x86_64 gnu/linux enterprise linux enterprise linux server release 5.3 (carthage) red hat enterprise linux server release 5.3 (tikanga) the 'bad' server newer: linux bad 2.6.18-371.4.1.el5 #1 smp wed jan 29 11:05:49 pst 2014 x86_64 x86_64 x86_64 gnu/linux oracle linux server release 5.10 red hat enterprise linux server release
Read more