A permutation is an ordering of a collection in which every element appears exactly once. Generating permutations systematically lets an algorithm examine every possible arrangement. section 8.2
A practical recursive strategy uses backtracking: swap an element into the current position, recursively arrange the remaining elements, then undo the swap before trying another choice. section 8.2
Generating permutations in Swift
A helper receives the current contents, an output array, and the number of positions still to arrange. When no positions remain, it records the arrangement. For ["a", "b", "c"], the function produces six orderings. The same results can become round trips by appending each path's first city to its end. section 8.2
Permutation generation supports several algorithmic tasks:
- Enumerate candidate routes for the traveling salesman problem. section 8.2
- Combine generated arrangements with distance lookups to select the shortest route. section 8.2
- Filter generated arrangements when only dictionary words or other constrained results are valid. section 8.6
Table 8.2. Driving distances between cities in Vermont
| Rutland |
Burlington |
White River Junction |
Bennington |
Brattleboro |
|
|---|---|---|---|---|---|
| Rutland | 0 | 67 | 46 | 55 | 75 |
| Burlington | 67 | 0 | 91 | 122 | 153 |
| White River Junction | 46 | 91 | 0 | 98 | 65 |
| Bennington | 55 | 122 | 98 | 0 | 40 |
| Brattleboro | 75 | 153 | 65 | 40 | 0 |
Use the distance table to connect each permutation of cities with a route length. section 8.2
