Union Of Two Bags
November 8, 2019
Today’s exercise is somebody’s homework:
A bag is a list of key/count pairs: for instance, a bag containing three of item E, three of item R, and three of item A can be written E3R3A3. The union of two bags is a single bag containing a list of key/count pairs in which each item in each of the two bags has its count combined in a single item: for instance, the union of bags E3R3A3 and B3R3F3 is E3R6A3B3F3. The order of items in the bags is not significant.
Your task is to write three programs to compute the union of two bags, with time complexities O(mn), O((m+n) log (m+n)), and O(m+n), where m and n are the sizes of the two bags. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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.