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).
(import (scheme base) (scheme write) (only (srfi 1) fold filter) (only (srfi 95) sorted? sort) ;; (only (org eip10 okmij myenv) assert) ) (define sample-bag-strings '("E3R3A3" "B3R3F3")) ;; We store bags as alists of positive counts with no repeated keys: ;; ((key . count) ...) (define sample-bags '(((A . 3) (E . 3) (R . 3)) ((B . 3) (F . 3) (R . 3)))) (define (bag-union/quadratic bag0 bag1 item=?) (fold (lambda (pr res) (cond ((assoc (car pr) bag1 item=?) => (lambda (b1pr) (cons (cons (car pr) (+ (cdr pr) (cdr b1pr))) res))) (else (cons pr res)))) (filter (lambda (pr) (not (assoc (car pr) bag0))) bag1) bag0)) (display (bag-union/quadratic (car sample-bags) (cadr sample-bags) eqv?)) (newline) (define (bag-union/nlogn bag0 bag1 item<?) (define (pr<? pr0 pr1) (item<? (car pr0) (car pr1))) (sorted-bag-union/linear (sort bag0 pr<?) (sort bag1 pr<?) item<?)) (define (symbol<? s0 s1) (string<? (symbol->string s0) (symbol->string s1))) (display (bag-union/nlogn (car sample-bags) (cadr sample-bags) symbol<?)) (newline) (define (sorted-bag-union/linear sbag0 sbag1 item<?) (define (pr<? pr0 pr1) (item<? (car pr0) (car pr1))) ;; (assert (sorted? sbag0 pr<?) (sorted? sbag1 pr<?)) (let loop ((sbag0 sbag0) (sbag1 sbag1) (res '())) (cond ((null? sbag0) (append (reverse res) sbag1)) ((null? sbag1) (append res sbag0)) ((item<? (caar sbag0) (caar sbag1)) (loop (cdr sbag0) sbag1 (cons (car sbag0) res))) ((item<? (caar sbag1) (caar sbag0)) (loop sbag0 (cdr sbag1) (cons (car sbag1) res))) (else (loop (cdr sbag0) (cdr sbag1) (cons (cons (caar sbag0) (+ (cdar sbag0) (cdar sbag1))) res)))))) (display (sorted-bag-union/linear (car sample-bags) (cadr sample-bags) symbol<?)) (newline)In my earlier code, there is a missing reverse in the third cond clause.
Here’s a solution in Python.
def union1(b1, b2): out1 = list(b1) out2 = [] for key2, val2 in b2: for idx, (key1, val1) in enumerate(out1): if key1 == key2: out1[idx] = (key1, val1 + val2) break else: out2.append((key2, val2)) return out1 + out2 def union2(b1, b2): out = [] b = sorted(b1 + b2) while b: key, val = b.pop() while b and b[-1][0] == key: val += b.pop()[1] out.append((key, val)) return out def union3(b1, b2): out = dict(b1) for key, val in b2: out[key] = out.get(key, 0) + val return list(out.items()) b1 = [('e', 3), ('r', 3), ('a', 3)] b2 = [('b', 3), ('r', 3), ('f', 3)] print(union1(b1, b2)) print(union2(b1, b2)) print(union3(b1, b2))Output:
[('e', 3), ('r', 6), ('a', 3), ('b', 3), ('f', 3)] [('r', 6), ('f', 3), ('e', 3), ('b', 3), ('a', 3)] [('e', 3), ('r', 6), ('a', 3), ('b', 3), ('f', 3)]Solutions in Racket.