Multiset

Multiset

A multiset (also known as a bag) is a data structure similar to a regular set, but it can store multiple instances of the same element.

For example, if I added the elements 1, 2, 2 to a regular set, the set would only contain two items, since adding 2 a second time has no effect.

var set = Set<Int>()
set.add(1) // set is now [1]
set.add(2) // set is now [1, 2]
set.add(2) // set is still [1, 2]

By comparison, after adding the elements 1, 2, 2 to a multiset, it would contain three items.

var set = Multiset<Int>()
set.add(1) // set is now [1]
set.add(2) // set is now [1, 2]
set.add(2) // set is now [1, 2, 2]

You might be thinking that this looks an awful lot like an array. So why would you use a multiset? Let's consider the differences between the two…

• Ordering: arrays maintain the order of items added to them, multisets do not
• Testing for membership: testing whether an element is a member of the collection is O(N) for arrays, O(1) for multisets.
• Testing for subset: testing whether collection X is a subset of collection Y is a simple operation for a multiset, but complex for arrays

Typical operations on a multiset are:

• Add an element
• Remove an element
• Get the count for an element (the number of times it's been added)
• Get the count for the whole set (the number of items that have been added)
• Check whether it is a subset of another multiset

One real-world use of multisets is to determine whether one string is a partial anagram of another. For example, the word "cacti" is a partial anagrams of "tactical". (In other words, I can rearrange the letters of "tactical" to make "cacti", with some letters left over.)

var cacti = Multiset<Character>("cacti")
var tactical = Multiset<Character>("tactical")
cacti.isSubSet(of: tactical) // true!

Implementation

Under the hood, this implementation of Multiset uses a dictionary to store a mapping of elements to the number of times they've been added.

Here's the essence of it:

public struct Multiset<Element: Hashable> {
  private var storage: [Element: UInt] = [:]
  
  public init() {}

And here's how you'd use this class to create a multiset of strings:

var set = Multiset<String>()

Adding an element is a case of incrementing the counter for that element, or setting it to 1 if it doesn't already exist:

public mutating func add (_ elem: Element) {
  storage[elem, default: 0] += 1
}

Here's how you'd use this method to add to the set we created earlier:

set.add("foo")
set.add("foo") 
set.allItems // returns ["foo", "foo"]

Our set now contains two elements, both the string "foo".

Removing an element works much the same way as adding; decrement the counter for the element, or remove it from the underlying dictionary if its value is 1 before removal.

public mutating func remove (_ elem: Element) {
  if let currentCount = storage[elem] {
    if currentCount > 1 {
      storage[elem] = currentCount - 1
    } else {
      storage.removeValue(forKey: elem)
    }
  }
}

Getting the count for an item is simple: we just return the value for the given item in the internal dictionary.

public func count(for key: Element) -> UInt {
  return storage[key] ?? 0
}

Written for the Swift Algorithm Club by Simon Whitaker