## 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.

Pages: 1 2

### 4 Responses to “Union Of Two Bags”

1. chaw said

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

``` (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) ```

2. chaw said

In my earlier code, there is a missing reverse in the third cond clause.

3. Daniel said

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] == key:
val += b.pop()
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)]
```
4. r. clayton said

Solutions in Racket.