Set operations (union, intersection) on Swift array?

Question

Are there any standard library calls I can use to either perform set operations on two arrays, or implement such logic myself (ideally as functionally and also efficiently as possible)?

Answer 1

Yes, Swift has the Set class.

let array1 = ["a", "b", "c"]
let array2 = ["a", "b", "d"]

let set1:Set<String> = Set(array1)
let set2:Set<String> = Set(array2)

Swift 3.0+ can do operations on sets as:

firstSet.union(secondSet)// Union of two sets
firstSet.intersection(secondSet)// Intersection of two sets
firstSet.symmetricDifference(secondSet)// exclusiveOr

Swift 2.0 can calculate on array arguments:

set1.union(array2)       // {"a", "b", "c", "d"} 
set1.intersect(array2)   // {"a", "b"}
set1.subtract(array2)    // {"c"}
set1.exclusiveOr(array2) // {"c", "d"}

Swift 1.2+ can calculate on sets:

set1.union(set2)        // {"a", "b", "c", "d"}
set1.intersect(set2)    // {"a", "b"}
set1.subtract(set2)     // {"c"}
set1.exclusiveOr(set2)  // {"c", "d"}

If you're using custom structs, you need to implement Hashable.

Thanks to Michael Stern in the comments for the Swift 2.0 update.

Thanks to Amjad Husseini in the comments for the Hashable info.

Answer 2

Swift Set operations

Example

let a: Set = ["A", "B"]
let b: Set = ["B", "C"]

union of A and B a.union(b)

let result = a.union(b)

var a2 = a
a2.formUnion(b)

//["A", "B", "C"]

symmetric difference of A and B a.symmetricDifference(b)

let result = a.symmetricDifference(b)
//["A", "C"]

difference A \ B a.subtracting(b)

let result = a.subtracting(b)
//["A"]

intersection of A and B a.intersection(b)

let result = a.intersection(b)
//["B"]

Please note that result order depends on hash

[Swift Set]

Answer 3

The most efficient method I know is by using godel numbers. Google for godel encoding.

The idea is so. Suppose you have N possible numbers and need to make sets of them. For example, N=100,000 and want to make sets like {1,2,3}, {5, 88, 19000} etc.

The idea is to keep the list of N prime numbers in memory and for a given set {a, b, c, ...} you encode it as

 prime[a]*prime[b]*prime[c]*...

So you encode a set as a BigNumber. The operations with BigNumbers, despite the fact that they are slower than operations with Integers are still very fast.

To unite 2 sets A, B, you take

  UNITE(A, B) = lcm(a, b)

lowest-common-multiple of A and B as A and B are sets and both numbers.

To make the intersection you take

 INTERSECT(A, B) = gcd (a, b)

greatest common divisor.

and so on.

This encoding is called godelization, you can google for more, all the language of arithmetics written using the logic of Frege can be encoded using numbers in this way.

To get the operation is-member? it is very simple --

ISMEMBER(x, S) = remainder(s,x)==0

To get the cardinal it's a little more complicated --

CARDINAL(S) = # of prime factors in s

you decompose the number S representing the set in product of prime factors and add their exponents. In case the set does not allow duplicates you will have all exponents 1.

Answer 4

There aren't any standard library calls, but you may want to look at the ExSwift library. It includes a bunch of new functions on Arrays including difference, intersection and union.

Answer 5

You may want to follow same pattern as in Objective-C, which also lacks such operations, but there is a simple workaround:

how to intersect two arrays in objective C?