CODEWITHSUNDEEP
swiftcollectionssetmultiset
Jeremy Cochoy
Jeremy Cochoy

Reputation: 2642

Swift how to make a set with multiplicity (multiset)

I am substracting two Array of Integers. I did the substraction using sets :

let numbersA = [1, 2, 3]
let numbersB = [3, 4, 5]
Set(numbersA).subtracting(numbersB)

but I then realized that I have multiplicity in my arrays, and I should take it into account. What is the data structure for multisets in Swift?

Upvotes: 0

Views: 1500

Answers (2)

Cortado-J
Cortado-J

Reputation: 2257

As you say, swift does not have Multiset as a native type. I implemented a fairly thorough implementation of Multiset in Swift here:

https://github.com/Cortado-J/Multiset

and full documentation of that library with usage examples here:

https://cortado-j.github.io/Multiset/Structs/Multiset.html

Upvotes: 0

Jeremy Cochoy
Jeremy Cochoy

Reputation: 2642

In swift 5, there is no Multiset implementation in the core library. You can reproduce the Multiset behavior by using a dictionary [Element:Multiplicity].

Your code will be:

let numbersA = [1, 2, 3, 3]
let numbersB = [3, 4, 5]
Set(numbersA).subtracting(numbersB) // [1, 2, 3]

As pointed out by Leo Dabus in comment, this gives you an unordered collection as a result.

You can find a good tutorial on multisets at https://github.com/raywenderlich/swift-algorithm-club/tree/master/Multiset

Here is a ready to use implementation of multiset. I added to it the substracting implementation. Notice it can be considered an incomplet implementation of a Multiset since, for exemple, it doesn't extends the Collection protocol.

//
//  Multiset.swift
//  Multiset
//
//  Created by Simon Whitaker on 28/08/2017.
//
//  Extended by Jeremy Cochoy on 17/11/2019

import Foundation

public struct Multiset<T: Hashable> {
  private var storage: [T: UInt] = [:]
  public private(set) var count: UInt = 0

  public init() {}

  public init<C: Collection>(_ collection: C) where C.Element == T {
    for element in collection {
      self.add(element)
    }
  }

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

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

  public func isSubSet (of superset: Multiset<T>) -> Bool {
    for (key, count) in storage {
      let supersetcount = superset.storage[key] ?? 0
      if count > supersetcount {
        return false
      }
    }
    return true
  }

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

  public var allItems: [T] {
    var result = [T]()
    for (key, count) in storage {
      for _ in 0 ..< count {
        result.append(key)
      }
    }
    return result
  }

  public func subtracting(_ elems: [T]) -> Multiset<T> {
    var resultSet = self
    elems.forEach { resultSet.remove($0) }
    return resultSet
  }
}

// MARK: - Equatable
extension Multiset: Equatable {
  public static func == (lhs: Multiset<T>, rhs: Multiset<T>) -> Bool {
    if lhs.storage.count != rhs.storage.count {
      return false
    }
    for (lkey, lcount) in lhs.storage {
      let rcount = rhs.storage[lkey] ?? 0
      if lcount != rcount {
        return false
      }
    }
    return true
  }
}

// MARK: - ExpressibleByArrayLiteral
extension Multiset: ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: T...) {
    self.init(elements)
  }
}

Upvotes: 1

Related Questions