Swift Algorithms: Getting Started

Working With Unique

You’ve probably encountered many situations where you needed to get the unique values from a collection and you wrote code to do that. Now you can try to implement this with Swift Algorithms.

The playground comes with sample data in marvelProductionYears showing all the Marvel movies and the year they in which they were made. 2008 had two movies, so it’s in the collection twice. Try to filter that collection down to just a single item for each year that a Marvel movie was released.

Add the following to your Unique playground page:

var uniqueYears = Set<Int>(marvelProductionYears)

print(Array(uniqueYears))

This is the simplest way to find the unique values from an array: Create a set from the array and you’re done. By definition, sets don’t store duplicate values. If you attempt to add an item that’s already present to the set, nothing will happen. This sounds easy, but there’s a small hole in this implementation. The values in the console are as follows:

[2017, 2013, 2014, 2008, 2016, 2018, 2019, 2012, 2011, 2015, 2010]

Yours might be different. But as you can see, there is no order. The original array was ordered, but when you iterated over the set, it gave a completely different order. There’s a simple solution for this; add the following line to your playground:

print(marvelProductionYears.uniqued())

Call uniqued() on any sequence and it’ll give you an array of only the unique values while maintaining the order of their appearance in the original sequence. The values in your console are ordered like this:

[2008, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019]

uniqued() has a constraint requirement on the element type: It must conform to Hashable. Otherwise, the sequence won’t have this method available.

Random Sampling

The standard library provides an easy way of getting a random value from a sequence: Sequence.randomElement(). But this may not be enough.

Consider for a moment that you want to watch some Marvel movies, chosen at random, but you don’t want to watch an older movie after a newer one.

Add the following code to your Random Sampling playground page:

var moviesToWatch: [String] = []
var numberOfMovies = 4

for _ in 1...numberOfMovies {
  moviesToWatch.append(marvelMovies.randomElement()!)
}

print(moviesToWatch)

This code takes four random movies from the array. Sometimes the results will be fine, but most of the time they aren’t.

Consider the following possible result:

["Black Panther", "Iron Man", "Captain Marvel", "Thor: Ragnarok"]

This isn’t the correct order of the movie releases. The correct order is:

["Iron Man", "Thor: Ragnarok", "Black Panther", "Captain Marvel"]

There are simple ways to get a pseudo-random in-order sample. But there are also ways to implement this algorithm properly, which is what Swift Algorithms does for you.

So now, add the following:

print(marvelMovies.randomStableSample(count: numberOfMovies))

Sequence.randomStableSample(count:) will choose count random items from the collection ensuring the order from the original collection is maintained.

Working With Indexed

It’s common to use enumerated() to iterate over a collection. It provides a sequence of pairs: an integer — which starts from zero — and a value.

Add the following code to your Indexed playground page:

let numbers = Array(1...50)
var matchingIntIndices: Set<Int> = []
for (i, number) in numbers.enumerated() {
  if number.isMultiple(of: 20) {
    matchingIntIndices.insert(i)
  }
}

print(matchingIntIndices)

In the code above, you created an array of integers with values from 1 to 50, and then you created a set to store the indices of the items that are multiples of 20.

The output of this code is:

[39, 19]

This code works great as long as the array you’re looping on has a zero-based index. But if you’re going through an ArraySlice and want to get the proper indices, it won’t match. Add the following code to the same playground page:

matchingIntIndices = []
let subArray = numbers[10...]

for (i, number) in subArray.enumerated() {
  if number.isMultiple(of: 20) {
    matchingIntIndices.insert(i)
  }
}

print(matchingIntIndices)

Here you created a slice from the original array, starting from index 10 and continuing to the end of the array. The resulting indices are 9 and 29. These are the indices in the slice of the original collection.

You can use Swift Algorithms to help. Add the following to your playground:

var matchingIndices: Set<Int> = []
for (i, number) in subArray.indexed() {
  if number.isMultiple(of: 20) {
    matchingIndices.insert(i)
  }
}

print(matchingIndices)

The output of this code is identical to the output in the previous example. Here you are using indexed() from Swift Algorithms to iterate the sub-array but maintaining the indices from the original array.

Working With Partition

Coming back to Marvel movies, say you want to watch them all in order, but break them down into Avengers movies and non-Avengers movies. The standard library already has a method for doing this: Collection.partition(by:). This reorders the collection by placing all the elements that pass the provided expression at the end of the collection, and it returns the index of the first item of those elements after reordering.

Try the following code on your Partition playground page:

var movies = marvelMoviesWithYears
let index = movies.partition { $0.0.contains("Avengers") }

for movie in movies[index...] {
  print(movie)
}

You’ll see the following output:

("Avengers: Infinity War", 2018)
("Avengers: Age of Ultron", 2015)
("Avengers: Endgame", 2019)
("The Avengers", 2012)

Notice that after partitioning, the array of movies has lost its order. Fortunately, Swift Algorithms provides a different kind of partition method to keep things ordered.

Add the following to your playground:

var movies2 = marvelMoviesWithYears
let index2 = movies2.stablePartition { $0.0.contains("Avengers") }

for movie in movies2[index2...] {
  print(movie)
}

The index will be the same as expected, but the partitions of the array are still ordered the same way they are in the original array.

It’s worth noting that if you use the first method on an already ordered collection and the expression is the same one used for the ordering, no swapping will occur and you’ll get the index of the item that satisfies the partitioning. Try the following:

var orderedMovies = marvelMoviesWithYears
let index3 = orderedMovies.partition { $0.1 > 2015 }

orderedMovies is still ordered even after calling the unstable partitioning method because the expression for the partitioning and the ordering criteria are the same. In this example, the index is 12.

You can find out if the collection is already partitioned using the new method, partitioningIndex(where:). If the resulting index is within the array, then it’s already ordered. But if it’s after the last element, then it isn’t.

Try the following two examples:

if marvelMoviesWithYears.partitioningIndex(where: { $0.0.contains("Avengers") }) < marvelMoviesWithYears.count {
  print("Array is ordered")
} else {
  print("Array is not properly ordered") // This will be printed
}

if marvelMoviesWithYears
  .partitioningIndex(where: { $0.1 > 2015 }) < marvelMoviesWithYears.count {
  print("Array is ordered") // This will be printed
} else {
  print("Array is not properly ordered")
}

The first example will print "Array is not properly ordered", but the second one will print "Array is ordered".