Swift Algorithms: Getting Started

Algorithms are an integral part of any software development. Whether it’s sorting a list of items or finding the unique elements in a collection, algorithms come in handy. To help us all out, Apple announced the new Swift Algorithms package in October 2020. It extends the capabilities of sequences and collections with a set of methods that can improve your daily code. You’ll learn all about this new package in this Swift Algorithms package tutorial!

In this tutorial, you’ll learn:

• What the Swift Algorithms package is
• Which algorithms are in the package
• How to use the algorithms

Feedback and contributions from the community will help grow this package. However, the package isn’t intended to be a reference for known algorithms like Swift Algorithm Club is. Rather, its purpose is to address some common operations that you use in different algorithms. So don’t expect it to build a binary tree for you. :]

Getting Started

Download the starter project by clicking the Download Materials button at the top or bottom of the tutorial. Unzip it and open SwiftAlgorithms.xcworkspace in the starter folder.

Next, you need to install the Swift Algorithms package through the Swift Package Manager. In Xcode, choose File ▸ Swift Packages ▸ Add Package Dependency. In the text field, add the URL https://github.com/apple/swift-algorithms and click Next. Then, on the last screen, specify Exact as the version type and 0.0.2 as the version. Now, click Next

Click Finish on the final screen.

Next, select the project file from the Project navigator, then select the UbrellaFramework target. On the Build Phases tab, add Algorithms to the Dependencies list.

Feel free to look at the starter project in the Project navigator.

The project consists of a framework and a collection of playground pages. You’ll use each page of the playground to showcase a different part of Swift Algorithms. You’ll also find SampleData.swift with some mock data, along with Utilities.swift, which contains some helper methods.

As a small aside, you may be asking yourself why this framework isn’t part of the Swift standard library. If it were, its updates would be tied to OS updates. But the intention of this framework is to evolve quickly and separately from Xcode and OS updates.

Now, without further ado, it’s time to dive in to the algorithms!

Working With Combinations

Combinations is a mathematical term that describes the possible combinations of a set of items from a larger set without duplication of any items and with complete disregard to ordering.

If you have a set consisting of the three items — “A”, “B” and “C” — you can have three possible combinations choosing any two of those three:

1. “A” + “B”
2. “A” + “C”
3. “B” + “C”

The set “B” + “A” is identical to “A” + “B”, since the order doesn’t matter. With the same example, if the size of the combination’s set is three, you’ll only have one possible combination: “A” + “B” + “C”. This is exactly the same as the main set.

Consider calculating the possible number of combinations with a large set of five, choosing any two items. This is written as 5 C 2.

It’s calculated as:

5 × 4 × 3 × 2 × 1 / (3 × 2 × 1) × (2 × 1)

To explain it in a more convenient way:

Factorial(5) / Factorial(5 - 2) × Factorial(2).

Using the factorial of a number means you recursively multiply a number with the number below it until you reach one. The sample project already has the implementation you need for factorial().

Open SwiftAlgorithms.playground and, on the Combinations playground page, add the following:

func numberOfCombinations(_ total: Int, setSize: Int) -> Double {
  return total.factorial() / 
    ((total - setSize).factorial() * setSize.factorial() )
}

This new function will calculate the number of possibilities for you. Try it with a few different numbers by adding the following code at the end of the playground:

numberOfCombinations(4, setSize: 2) // 6
numberOfCombinations(6, setSize: 2) // 15
numberOfCombinations(6, setSize: 3) // 20
numberOfCombinations(6, setSize: 6) // 1

Run the playground and you’ll see the results in the playground’s results pane.

You can calculate one of the numbers yourself to make sure you understand it.

What you’ve manually done here is exactly what Swift Algorithms provides natively. To see it in action, add the following code at the end of the playground:

let exampleCombinations = ["A", "B", "C"].combinations(ofCount: 2)

for set in exampleCombinations {
  print(set)
}

combinations(ofCount:) from Swift Algorithms calculates all the combinations of a sequence when choosing a certain number of them.

The results in the console log look like this:

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

For a larger example, imagine you want to calculate all the possible match-ups for the clubs in the Premier League. Fortunately, there’s already a premierLeagueClubs constant in SampleData.swift:

let clubCombinations = premierLeagueClubs.combinations(ofCount: 2)

Now get the count of all those possible combinations, and compare that result to the function you added in the beginning:

clubCombinations.count // 190
numberOfCombinations(premierLeagueClubs.count, setSize: 2) // 190

Both values are the same. Since the Premier League has 20 clubs, then:

20 C 2 = 20 × 19 / 2 = 190

Print the list of match-ups:

for teamups in clubCombinations {
  print(teamups)
}

It’ll show you a long list, and each is an array of two clubs:

["Arsenal", "Aston Villa"]
["Arsenal", "Brighton & Hove Albion"]
.
.
.
.
["West Bromwich Albion", "Wolverhampton Wanderers"]
["West Ham United", "Wolverhampton Wanderers"]

That’s neat and handy right! Well, there’s more where that came from. Time to look at another similar algorithm.

Working With Permutations

The next item in the package is Permutations. It’s similar to combinations where you want to choose a certain number of items from a collection, but it’s concerned with the order of the items. This means the possible permutations for the group “A” and “B”, for a set of two items, are:

1. “A” + “B”
2. “B” + “A”

Following the same numerical example in combinations, the number of permutations of a group of five items choosing any 2, or “5 P 2” is:

5 × 4 × 3 × 2 × 1 / (3 × 2 × 1)

Its mathematical equation is:

Factorial(5) / Factorial(5 - 2)

The difference between the equations of permutations and combinations is the latter divides by the factorial of the set size. An example calculation is:

5 P 5 = Factorial(5) / Factorial(1) = (5 × 4 × 3 × 2 × 1) / 1 = 120

On your Permutations playground page, add the following:

func numberOfPermutations(_ total: Int, setSize: Int) -> Double {
  return total.factorial() / (total - setSize).factorial()
}

Like before, this equation calculates the number of total results but not the results themselves. Add the following:

numberOfPermutations(4, setSize: 2) // 12
numberOfPermutations(6, setSize: 2) // 30
numberOfPermutations(6, setSize: 6) // 720

Earlier, you calculated the number of match-ups between teams, but the result isn’t the actual number of matches, because every two teams play against each other twice — once on their home field and once as a visitor.

So in this example, permutations is the way to calculate the number of matches and what those matches are. The first team in each result is the home team, and the second one is the visitor.

Calculate how many matches there are:

let permutations = premierLeagueClubs.permutations(ofCount: 2)
permutations.count // 380

This uses permutations(ofCount:) from Swift Algorithms. You can check the count is correct using the method you just added:

numberOfPermutations(premierLeagueClubs.count, setSize: 2) // 380

The number of permutation results is twice the number of combination results, which makes sense, given that the teams play against one another twice.

Add the following to print the matches themselves:

for matches in permutations {
  print(matches)
}

The results in your log will look like this:

["Arsenal", "Aston Villa"]
["Arsenal", "Brighton & Hove Albion"]
.
.
.
["Wolverhampton Wanderers", "West Bromwich Albion"]
["Wolverhampton Wanderers", "West Ham United"]