Swift Algorithmsを軽く触ってみた

どーも🙏 jollyjoesterです。

これはSwiftKotlin愛好会アドベントカレンダー 2020の1日目の記事です。
今日はすでに12/26ですがアドベントカレンダー終わってから１日目、諦めずに頑張っていきたいと思いますｗ

[Swift.orgのブログ](https://swift.org/blog/swift-algorithms/)で紹介されていたSwift Algorithmsが気になっていたのにスルーしていたので、あらためて見てみたいと思います。

## Swift Algorithmsとは？

SequenceとCollectionに関するアルゴリズムをOpen Sourceとしてまとめたものです。下記のアルゴリズムが含まれているようです。

- Combinations / Permutations
- Product
- Chunked
- Chain
- Cycle
- Unique
- Random Sampling
- Indexed
- Partition
- Rotate

どんな動きをするかは[GitHubのGuides](https://github.com/apple/swift-algorithms/tree/main/Guides)に記載ありますが、手元で動かした方が理解が捗ると思います。

よければGuidesの内容をほぼそのまま動かせるようにした次のPlaygroundを使ってみてください。

[Swift Algorithms Playground](https://github.com/jollyjoester/SwiftAlgorithmsPlayground)

## 各アルゴリズムについて

### Combinations

コレクションから組合せ（nCr）を計算するメソッドです。
便利ですね！

```swift
import Algorithms

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]
```

### Permutations

コレクションから順列（nPr）を計算するメソッドです。

```swift
import Algorithms

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]
```

### Product

異なるコレクション同士の積（それぞれのコレクションの要素をかけあわせる）を作ります。

```swift
import Algorithms

let numbersInEnglish = ["one", "two", "three"]
for (number, numberInEnglish) in product(1...3, numbersInEnglish) {
    print("\(number)\(numberInEnglish)")
}

//1one
//1two
//1three
//2one
//2two
//2three
//3one
//3two
//3three
```

こちらと同等の処理ですが、productが使えるとわかりやすいですね。

```swift
for number in 1...3 {
    for numberInEnglish in numbersInEnglish {
        print("\(number)\(numberInEnglish)")
    }
}
```

### Chunked

Chunkは「かたまり」のことです。
コレクションを複数のサブシーケンスに分割します。

forで回して詰め直すみたなことやらなくてすみますね。

```swift
import Algorithms

let numbers = [10, 20, 30, 10, 40, 40, 10, 20]
let chunks1 = numbers.chunked(by: { $0 <= $1 })
print(chunks1)

// [ArraySlice([10, 20, 30]), ArraySlice([10, 40, 40]), ArraySlice([10, 20])]

let names = ["David", "Kyle", "Karoy", "Nate"]
let chunks2 = names.chunked(on: \.first)
print(chunks2)

// [ArraySlice(["David"]), ArraySlice(["Kyle", "Karoy"]), ArraySlice(["Nate"])]

```

### Chain

Chainは「鎖でつなぐ」という意味です。
要素の型が同じ２つのコレクションを連結します。

シンプル

```swift
import Algorithms

let numbers = chain([10, 20, 30], 1...5)
print(Array(numbers))

//[10, 20, 30, 1, 2, 3, 4, 5]

let letters = chain("abcde", "FGHIJ")
print(String(letters))

//abcdeFGHIJ
```


### Cycle

Cycleは「循環する」という意味です。
コレクションを無限にor指定された回数繰り返します。

```swift
import Algorithms

for x in (1...3).cycled(times: 3) {
    print(x)
}

//1
//2
//3
//1
//2
//3
//1
//2
//3
```

### Unique

Uniqueは「一意の」という意味です。
コレクションから重複する要素を削除したコレクションを返します。

```swift
import Algorithms

let numbers = [1, 2, 3, 3, 2, 3, 3, 2, 2, 2, 1]
let unique = numbers.uniqued()

print(unique)

//[1, 2, 3]
```

### Random Sampling

コレクションから指定した数の要素をランダムに抽出したコレクションを返します。
randomStableSampleの方を使うと抽出された要素の順番が維持されます。

```swift
import Algorithms

var source = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

let sample1 = source.randomSample(count: 4)
print(sample1)

// [70, 30, 10, 50]

let sample2 = source.randomStableSample(count: 4)
print(sample2)

//[20, 60, 80, 90]
```

### Indexed

コレクションの各インデックスと要素をペアにします。

```swift
import Algorithms

let numbers = [10, 20, 30, 40, 50]
var matchingIndices: Set<Int> = []
for (i, n) in numbers.indexed() {
    if n.isMultiple(of: 20) {
        matchingIndices.insert(i)
    }
}
print(matchingIndices)

//[3, 1]
```

### Partition

特定の条件を元にコレクションを並べ替える処理です。
元のコレクションの順番を維持する、しないメソッドがそれぞれあります。

```swift
var numbers1 = [10, 20, 30, 40, 50, 60, 70, 80]
let p1 = numbers1.partition(by: { $0.isMultiple(of: 20) })
print(p1)
print(numbers1)

//4
//[10, 70, 30, 50, 40, 60, 20, 80]

numbers1 = [10, 20, 30, 40, 50, 60, 70, 80]
let p2 = numbers1.stablePartition(by: { $0.isMultiple(of: 20) })
print(p2)
print(numbers1)

// p2 == 4
// numbers == [10, 30, 50, 70, 20, 40, 60, 80]
```

PartitionされたIndexを利用することもできます。

```swift
let numbers2 = [10, 30, 50, 70, 20, 40, 60]
let p = numbers2.partitioningIndex(where: { $0.isMultiple(of: 20) })

print(numbers2[..<p])
print(numbers2[p...])

//[10, 30, 50, 70]
//[20, 40, 60]
```

### Rotate

指定した要素を先頭に来るように並べ替える（回転？）処理です。
レンジを指定して並べ替えることもできます。

```swift
import Algorithms

var numbers1 = [10, 20, 30, 40, 50, 60]
let p = numbers1.rotate(toStartAt: 2)
print(p)
print(numbers1)

//4
//[30, 40, 50, 60, 10, 20]

var numbers2 = [10, 20, 30, 40, 50, 60]
numbers2.rotate(subrange: 0..<3, toStartAt: 1)
print(numbers2)

//[20, 30, 10, 40, 50, 60]

numbers2.rotate(subrange: 3..<6, toStartAt: 4)
print(numbers2)

//[20, 30, 10, 50, 60, 40]
```

## まとめ

コレクションを処理する方法について、便利〜って処理から既存の方法で同じことができるけど表現力が上がったようなものまで様々ありましたね！

まだまだバージョンが0.0.2とできたばかりなので今後が楽しみです。

# Refs

- Swift AlgorithmsのGitHubリポジトリ
  - https://github.com/apple/swift-algorithms
- Swift.orgでのSwift Algorithmsのブログ
 - https://swift.org/blog/swift-algorithms/
- Swift Algorithmsを解説したInfoQの記事
 - https://www.infoq.com/jp/news/2020/11/swift-algorithms-open-sourced/
- 関連として様々なアルゴリズムをSwiftで実装が解説されているGitHubリポジトリ
 - https://github.com/raywenderlich/swift-algorithm-club/