最近 Swift 社区动作频频，又是登陆 Windows，又是推出底层基础库。现在又推出了 Swift 算法库，现在让我们看看里面到底有什么内容，是否值得现在在生产中应用，面对内容丰富的 raywenderlich/swift-algorithm-club 是否有足够的竞争力呢。
介绍
仓库地址：https://github.com/apple/swift-algorithms
目前项目还是 0.0.1 版，只提供 SwiftPM 包管理支持。一共包含 11 种算法，仅针对序列与集合类型，包含的算法如下：
- 排列与组合类算法：Combinations / Permutations
- 变换类算法：Rotate / Partition
- 集合合并类算法：Chain / Product / Cycle
- 子集合操作算法：Random Sampling / Unique
- 其他操作算法：Chunked / Indexed
使用方法
在 Xcode 11 及以上已经集成了 Swift Package 的使用，在 project 的设置中添加一个 package 即可，地址：https://github.com/apple/swift-algorithms, 选择 0.0.1 版本。
如果使用 Package.swift 文件，添加如下内容：
let package = Package(
// name, platforms, products, etc.
dependencies: [
.package(url: "https://github.com/apple/swift-algorithms", from: "0.0.1"),
// other dependencies
],
targets: [
.target(name: "<target>", dependencies: [
.product(name: "Algorithms", package: "swift-algorithms"),
]),
// other targets
]
)排列组合
Combinations
Combinations 主要用来生成集合的所有可能组合结果，如果有两个元素值相同也算作不同的元素，用法如下：
let numbers = [10, 20, 30, 40]
for combo in numbers.combinations(ofCount: 2) {
print(combo)
}
// [10, 20]
// [10, 30]
// [10, 40]
// [20, 30]
// [20, 40]
// [30, 40]
let numbers2 = [20, 10, 10]
for combo in numbers2.combinations(ofCount: 2) {
print(combo)
}
// [20, 10]
// [20, 10]
// [10, 10]Combinations 结构体实现了 Sequence 协议，通过迭代来读取每种组合，如果需要直接得到所有结果，转成数组即可：
let numbers = [10, 20, 30, 40]
let combinedArray = Array(numbers.combinations(ofCount: 3))
print(combinedArray)
// [[10, 20, 30], [10, 20, 40], [10, 30, 40], [20, 30, 40]]Permutations
Permutations 用于生成集合的全排列，也是通过遵守 Sequence 协议的方式来实现，可以默认包含所有元素，也可以指定个数，同样相同的值作为不同的元素对待：
let numbers = [10, 20, 30]
for perm in numbers.permutations() {
print(perm)
}
// [10, 20, 30]
// [10, 30, 20]
// [20, 10, 30]
// [20, 30, 10]
// [30, 10, 20]
// [30, 20, 10]
for perm in numbers.permutations(ofCount: 2) {
print(perm)
}
// [10, 20]
// [10, 30]
// [20, 10]
// [20, 30]
// [30, 10]
// [30, 20]集合变换
Rotate
Rotate 用于将集合中的一段数据移动到最前面，如下面代码将 index = 2 开始的后面所有元素都移动到最前面，并返回原来最前面元素移动后的新 index：
var numbers = [10, 20, 30, 40, 50, 60]
let p = numbers.rotate(at: 2)
// numbers == [30, 40, 50, 60, 10, 20]
// p == 4还可以选择集合中的某一部分进行移动，下面将索引为 0..<3 范围内的元素，从 index = 1 处移动到该范围的最前面，范围外的其他元素保持不动：
var numbers = [10, 20, 30, 40, 50, 60]
numbers.rotate(subrange: 0..<3, at: 1)
// numbers = [20, 30, 10, 40, 50, 60]Rotate 算法经常用于解决分治算法中的写时复制与切片修改问题。
Partition
Partition 用于根据指定条件将集合划分为两个部分，符合条件的移动到集合末尾。
提供了以下几个方法：
stablePartition(by:)将符合闭包判断条件的元素移动至数组末尾，移动后的元素仍然保持原来的相对顺序，并返回移动后符合条件部分的第一个元素的索引（如果没有符合条件的元素，则返回数组末尾元素的下一个索引）：
numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let p2 = numbers.stablePartition(by: { $0.isMultiple(of: 20) })
// numbers = [10, 30, 50, 70, 20, 40, 60, 80]stablePartition(subrange:by:)在指定范围内并将符合条件的元素移动至范围的末尾：
numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let p2 = numbers.stablePartition(subrange: 1..<4, by: { $0.isMultiple(of: 20) })
// numbers = [10, 30, 20, 40, 50, 60, 70, 80]有一个问题需要注意一下：在 0.0.1 版本中 stablePartition(subrange:by:) 方法是有缺陷的，如果设定的 subrange 未覆盖全部集合元素将会报错，笔者已经对这个问题提交了一个 pr 并合并到了主干。
- 另外需要注意，swift 内置的集合方法中已经提供了一个
partition(by:)方法，但这个方法只是将符合条件的元素移动至末尾，并不保证元素移动后的相对位置，partition 的时间复杂度是 O(n),stablePartition的时间复杂度是O(n log n)：
var numbers = [10, 100, 30, 40, 50, 60, 70, 80]
let p2 = numbers.partition(by: { $0.isMultiple(of: 20) })
// numbers = [10, 70, 30, 50, 40, 60, 100, 80]还提供了一个方法，获取已经进行了 partition 操作的集合的第一个符合条件元素索引：
let numbers = [10, 30, 50, 70, 20, 40, 60]
let p = numbers.partitioningIndex(where: { $0.isMultiple(of: 20) })
// p = 4
// numbers[..<p] == [10, 30, 50, 70]
// numbers[p...] = [20, 40, 60]集合合并
Chain
Chain 用于将两个集合合并为一个集合：
let numbers = [10, 20, 30].chained(with: 1...5)
// Array(numbers) == [10, 20, 30, 1, 2, 3, 4, 5]
//
let letters = "abcde".chained(with: "FGHIJ")
// String(letters) == "abcdeFGHIJ"Chain 类型实现了 Sequence 与 Collection 协议，可以当成普通的集合类型来使用。
Product
Product 用于提供两个集合所有元素的俩俩配对组合的遍历支持：
let seasons = ["winter", "spring", "summer", "fall"]
for (year, season) in product(1900...2020, seasons) {
print(year, season)
}
// 1900 winter
// 1900 spring
// 1900 summer
// 1900 fall
// 1902 winter
// ..
// 2020 fallproduct 方法要求传入的第一个参数遵守 Sequence 协议，而第二个参数遵守 Collection 协议，因为第一个参数只需要遍历一次，而第二参数需要多次遍历，Sequence 协议不保证重复遍历输出一样的值。
Cycle
Cycle 提供无限遍历一个集合的能力：
for (odd, n) in zip([true, false].cycled(), 1...) {
print(odd, n)
}
// true 1
// false 2
// true 3
// false 4
// true 5
// false 6
// ...或者指定重复遍历的次数：
代码语言：javascript复制for x in (1...3).cycled(times: 3) {
print(x)
}
// 1 2 3 1 2 3 1 2 3cycled(times:) 方法组合了标准库中的 repeatElement 和 joined 方法，提供了更方便的有限次重复集合的方法。
子集合操作
Random Sampling
Random Sampling 提供了从集合中随机挑选元素形成新的集合的能力 ，每次执行的结果都可能不同：
var source = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
source.randomSample(count: 4)
// e.g. [30, 10, 70, 50]还提供了一个 randomStableSample(count:) 方法保证挑选之后的集合保持原有元素的相对顺序：
source.randomStableSample(count: 4)
// e.g. [20, 30, 80, 100]还可以自定义随机数生成方法：
代码语言：javascript复制var rng = SplitMix64(seed: 0)
source.randomSample(count: 4, using: &rng)Unique
Unique 可以去除集合中重复的元素，内部利用 Set 类型来实现：
let numbers = [1, 2, 3, 3, 2, 3, 3, 2, 2, 2, 1]
let unique = numbers.uniqued()
// unique == [1, 2, 3]还可以提供一个闭包来确定是否唯一：
代码语言：javascript复制let source = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
let uniq = source.uniqued { $0 % 12 }
// [10, 20, 30, 40, 50, 60]以上代码中，除以 12 余数相同的元素不再出现在结果中。
其他集合操作
Chunked
Chunked 可以将一个集合按照一定条件划分为包含多个子集的新集合：
let numbers = [10, 20, 30, 10, 40, 40, 10, 20]
let chunks = numbers.chunked(by: { $0 <= $1 })
// [[10, 20, 30], [10, 40, 40], [10, 20]]以上代码根据 { 0 <= 1 } 这个闭包将原数组划分为多个升序子集合
还提供了一个 chunked(on:) 方法，根据其中闭包计算的结果比对是否相同，相同的元素在一个子集里：
let names = ["David", "Kyle", "Karoy", "Nate"]
let chunks = names.chunked(on: .first!)
// [["David"], ["Kyle", "Karoy"], ["Nate"]]以上代码将首字母相同的放在一个子集里。
Indexed
Indexed 将集合转换为一个新的集合，每个元素为一个包含了原集合元素的索引与值的元组：
let numbers = [10, 20, 30, 40, 50]
var matchingIndices: Set<Int> = []
for (i, n) in numbers.indexed() {
print(i, n)
}
// 0 10
// 1 20
// 2 30
// 3 40
// 4 50总结
从上面内容可以看到，Swift 算法库现在还比较简单，很多地方还待完善，等社区贡献了更多内容后未来还是值得期待的，以后不用再手写各种常用算法了。
