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.

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

  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][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)]
    
  4. r. clayton said

    Solutions in Racket.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: