Union Of Two Bags
November 8, 2019
We represent bags as lists of dotted pairs:
(define bag1 '((#\e . 3) (#\r . 3) (#\a . 3))) (define bag2 '((#\b . 3) (#\r . 3) (#\f . 3)))
The first solution iterates over the two bags, either creating a new key/count pair in a result bag if the current item is not in the result bag, or incrementing the count if it is; the time complexity is O(mn):
(define (update x xs) (let loop ((xs xs) (zs (list))) (if (null? xs) (cons x zs) (if (char=? (car x) (caar xs)) (append (cdr xs) zs (list (cons (car x) (+ (cdr x) (cdar xs))))) (loop (cdr xs) (cons (car xs) zs))))))
(define (union1 bag1 bag2) (let loop ((bag1 bag1) (bag2 bag2)) (if (null? bag1) bag2 (loop (cdr bag1) (update (car bag1) bag2))))))
> (union1 bag1 bag2) ((#\a . 3) (#\r . 6) (#\e . 3) (#\f . 3) (#\b . 3))
The second solution sorts the items in the two bags into a single list, then iterates over the list, combining adjacent items with equal keys; the time complexity is O((m+n) log (m+n)):
(define (union2 bag1 bag2) (define (lt? a b) (char<? (car a) (car b))) (let loop ((xs (sort lt? (append bag1 bag2))) (zs (list))) (if (null? xs) zs (if (null? zs) (loop (cdr xs) (cons (car xs) zs)) (if (char=? (caar xs) (caar zs)) (loop (cdr xs) (cons (cons (caar xs) (+ (cdar xs) (cdar zs))) (cdr zs))) (loop (cdr xs) (cons (car xs) zs)))))))
> (union2 bag1 bag2) ((#\r . 6) (#\f . 3) (#\e . 3) (#\b . 3) (#\a . 3))
The third solution first enters all of the items in one bag in a hash table, then iterates over the items in the other bag, updating the counts in the hash table for existing items or adding new items to the hash table; the time complexity is O(m+n):
(define (union3 bag1 bag2) (let ((ht (make-eq-hashtable))) (do ((xs (append bag1 bag2) (cdr xs))) ((null? xs) (vector->list (let-values (((ks vs) (hashtable-entries ht))) (vector-map cons ks vs)))) (hashtable-update! ht (caar xs) (lambda (x) (+ x (cdar xs))) 0))))
> (union3 bag1 bag2) ((#\f . 3) (#\b . 3) (#\a . 3) (#\r . 6) (#\e . 3))
You can run the program at https://ideone.com/aMoH8Q, although the Chicken Scheme at ideone doesn’t have hashtables so union3
doesn’t work.
Here is a solution in R7RS Scheme plus a few well-known helpers. It
is a bit more general than @programmingpraxis’s solution for bag
element types but uses a sorted representation of bags for the
linear-time version (instead of hashing).
In my earlier code, there is a missing reverse in the third cond clause.
Here’s a solution in Python.
Output:
Solutions in Racket.