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

Pase

A set can be implemented on top of a dictionary if you want to do it yourself. – Maidstone

@Maidstone Do you mean by using the keys to ensure uniqueness? – Pase

Could you just use `Dictionary<String, Void>? – Tippets

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.

Karoline

Note that, as of Swift 2.0 at least, you can pass an array as the argument to these functions. Thus, set1.union(array2) and set1.exclusiveOr(array2) are both legitimate, in addition to the forms shown above. – Enucleate

What if you want to intersect 5 arrays? Or 6? What if the number of arrays is unknown? – Matless

@Nathan Depends on the set operation. For example, set union and set intersection are commutative and associative, so you can process many sets by using iteration or chaining. Or you could create custom methods that use var args, such as Set union_all(...) and intersect_all(...). – Karoline

What about if your arrays contain duplicate values, for example to determine if $0 is an anagram of $1 where the input characters could have duplicate letters? – Hendershot

If you're using custom structs you have to conform Hashable, which might be annoying if you have a complicated struct – Neptune

As of Swift 4.0; Sets now also support the isDisjoint function. Maybe worthwhile to add? – Connie

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 a hash function result

[Swift Set]

Knitting

nice graphical explanation – Elsewhere

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.

Spang

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.

Bartz

A cautionary note: I'd been using ExSwift without issue for Swift 1.x but it seems quite broken for Swift 2.x, and as of this writing hasn't been updated in a few months. There are a ton of forks that may receive more attention. – Lammastide

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?

Sorrel