競プロで使えるアルゴリズム関数一覧(Swift)

私はSwiftにおける競プロの記事をいくつか投稿しています。

- [競プロで使える標準入力の便利メソッド一覧](https://qiita.com/uhooi/items/b8cebb638e9bf5ac9556)
- [競プロで使える標準エラーの出力方法](https://qiita.com/uhooi/items/f490d14602a7bc114948)
- [競プロで使える便利なエクステンション一覧](https://qiita.com/uhooi/items/ff1113c337d7a756d580)
- 競プロで使えるアルゴリズム関数一覧 __←イマココ__

自分で武器を増やしていくのが競プロの面白さのひとつだと思っているので、まずは自分で考えるのがオススメです。
どうしてもわからないときに、私の記事が参考になると嬉しいです :relaxed:

## はじめに

本記事は [Swift/Kotlin愛好会 Advent Calendar 2020](https://qiita.com/advent-calendar/2020/love_swift_kotlin) の6日目の記事です。
競プロで使えるアルゴリズムの関数を紹介します。

## 注意

- 本記事で紹介している関数および計算量が正しいかは保証できていません。  
- さらに計算量が小さいプログラムが存在する可能性があります。
- 本記事は随時更新予定です。

## 環境

- OS：macOS Big Sur 11.0.1
- Xcode：12.2 (12B45b)
- Swift：5.3.1  
5.2.1（2020/12/06現在のAtCoder）でも動作する

## 競プロで使えるアルゴリズム関数一覧

### 順列全探索

<details><summary>説明</summary><div>

TBD

</div></details>

<details><summary>ソースコード</summary><div>

```swift
private func permutations<T>(of values: [T]) -> [[T]] {
    if values.count <= 1 {
        return [values]
    }
    var results: [[T]] = []
    for i in values.indices {
        let baseValue = values[i]
        var excludingBaseValue = values
        excludingBaseValue.remove(at: i)
        results += permutations(of: excludingBaseValue).map { [baseValue] + $0 }
    }
    return results
}
```

</div></details>

<details><summary>出力例</summary><div>

```
[1, 3] -> [[1, 3], [3, 1]]
[1, 2, 4] -> [[1, 2, 4], [1, 4, 2], [2, 1, 4], [2, 4, 1], [4, 1, 2], [4, 2, 1]]
[1, 2, 3, 5] -> [[1, 2, 3, 5], [1, 2, 5, 3], [1, 3, 2, 5], [1, 3, 5, 2], [1, 5, 2, 3], [1, 5, 3, 2], [2, 1, 3, 5], [2, 1, 5, 3], [2, 3, 1, 5], [2, 3, 5, 1], [2, 5, 1, 3], [2, 5, 3, 1], [3, 1, 2, 5], [3, 1, 5, 2], [3, 2, 1, 5], [3, 2, 5, 1], [3, 5, 1, 2], [3, 5, 2, 1], [5, 1, 2, 3], [5, 1, 3, 2], [5, 2, 1, 3], [5, 2, 3, 1], [5, 3, 1, 2], [5, 3, 2, 1]]
```

</div></details>

<details><summary>計算量</summary><div>

TBD

</div></details>

<details><summary>参考リンク</summary><div>

TBD

</div></details>

### 階乗

<details><summary>説明</summary><div>

$n!$ を返します。

まだAtCoderでは使ったことがありません。

</div></details>

<details><summary>ソースコード</summary><div>

```swift
private func factorial(of value: Int) -> Int {
    precondition(value >= 0)
    if value == 0 {
        return 1
    }
    return (1...value).reduce(1, *)
}
```

</div></details>

<details><summary>出力例</summary><div>

```
0 -> 1
1 -> 1
2 -> 2
3 -> 6
9 -> 362880
```

</div></details>

<details><summary>計算量</summary><div>

$O(N)$

</div></details>

<details><summary>参考リンク</summary><div>

- [階乗 - Wikipedia](https://ja.wikipedia.org/wiki/階乗)

</div></details>

### 組み合わせ

<details><summary>説明</summary><div>

$_nC_r$ を返します。

</div></details>

<details><summary>ソースコード</summary><div>

```swift
private func combination(n: Int, r: Int) -> Int {
    precondition(n > 0 && r >= 0)
    if r == 0 {
        return 1
    }
    if r > n {
        return 0
    }
    var result = 1
    for i in 1...r {
        result *= n - (i - 1)
        result /= i
    }
    return result
}
```

$\frac{_nP_r}{r!}$ の分子から計算すると（ $n$ や $r$ の大きさによっては）64 bit 整数型ではオーバーフローするため、掛けて割ってを繰り返しています。
割る数値を $1, 2, \ldots, r$ と1から昇順に増やすことで、 `result` は常に整数となります。

</div></details>

<details><summary>出力例</summary><div>

```
(n: 1, r: 0) -> 1
(n: 1, r: 1) -> 1
(n: 1, r: 2) -> 0
(n: 2, r: 1) -> 2
(n: 11, r: 11) -> 1
(n: 12, r: 11) -> 12
(n: 13, r: 11) -> 78
(n: 16, r: 11) -> 4368
(n: 199, r: 11) -> 366461620334848584
```

</div></details>

<details><summary>計算量</summary><div>

$O(r)$

</div></details>

<details><summary>参考リンク</summary><div>

- [組合せ (数学) - Wikipedia](https://ja.wikipedia.org/wiki/組合せ_(数学))
- [解説 - AtCoder Beginner Contest 185](https://atcoder.jp/contests/abc185/editorial/358)
- [提出 #18756467 - AtCoder Beginner Contest 185](https://atcoder.jp/contests/abc185/submissions/18756467)
- [提出 #18768157 - AtCoder Beginner Contest 185](https://atcoder.jp/contests/abc185/submissions/18768157)

</div></details>

### 約数列挙

<details><summary>説明</summary><div>

与えられた数値の約数をすべて求め、昇順に整列した配列で返します。
整列する必要がない場合、返却時の `sorted()` を外してください。

</div></details>

<details><summary>ソースコード</summary><div>

```swift
import Foundation

private func divisors(of value: Int) -> [Int] {
    precondition(value > 0)
    var divisors: Set<Int> = []
    for i in 1...(Int(floor(sqrt(Double(value))))) where value % i == 0 {
        divisors.insert(i)
        divisors.insert(value / i)
    }
    return divisors.sorted()
}
```

`divisors` 変数を通常の配列でなく `Set<Int>` 型で定義している理由は、数値が平方数（例: 25）の場合に約数が重複するのを防ぐためです。
通常の配列は重複を許すため `25 -> [1, 5, 5, 25]` となりますが、 `Set<Int>` は重複を許さないので `25 -> [1, 5, 25]` となります。

</div></details>

<details><summary>出力例</summary><div>

```
1 -> [1]
2 -> [1, 2]
3 -> [1, 3]
4 -> [1, 2, 4]
5 -> [1, 5]
6 -> [1, 2, 3, 6]
7 -> [1, 7]
8 -> [1, 2, 4, 8]
9 -> [1, 3, 9]
10 -> [1, 2, 5, 10]
11 -> [1, 11]
12 -> [1, 2, 3, 4, 6, 12]
13 -> [1, 13]
14 -> [1, 2, 7, 14]
15 -> [1, 3, 5, 15]
16 -> [1, 2, 4, 8, 16]
17 -> [1, 17]
18 -> [1, 2, 3, 6, 9, 18]
19 -> [1, 19]
20 -> [1, 2, 4, 5, 10, 20]
21 -> [1, 3, 7, 21]
22 -> [1, 2, 11, 22]
23 -> [1, 23]
24 -> [1, 2, 3, 4, 6, 8, 12, 24]
25 -> [1, 5, 25]
26 -> [1, 2, 13, 26]
27 -> [1, 3, 9, 27]
28 -> [1, 2, 4, 7, 14, 28]
29 -> [1, 29]
30 -> [1, 2, 3, 5, 6, 10, 15, 30]
```

</div></details>

<details><summary>計算量</summary><div>

$O(\sqrt{N})$

</div></details>

<details><summary>参考リンク</summary><div>

- [提出 #173650 | アルゴ式](https://algo-method.com/submissions/173650)

</div></details>

### 素因数分解

<details><summary>説明</summary><div>

与えられた数値を素因数分解し、昇順に整列した配列で返します。

</div></details>

<details><summary>ソースコード</summary><div>

```swift
import Foundation

private func primeFactorizations(of value: Int) -> [Int] {
    precondition(value > 0)
    if (1...3).contains(value) {
        return [value]
    }

    var copiedValue = value
    var primeFactorizations: [Int] = []
    for i in 2...Int(floor(Double(n) / 2)) {
        while copiedValue % i == 0 {
            copiedValue /= i
            primeFactorizations.append(i)
        }
        if primeFactorizations.reduce(1, *) == value {
            break
        }
    }
    if primeFactorizations.isEmpty {
        primeFactorizations.append(value)
    }
    return primeFactorizations
}
```

</div></details>

<details><summary>出力例</summary><div>

```
1 -> [1]
2 -> [2]
3 -> [3]
4 -> [2, 2]
5 -> [5]
6 -> [2, 3]
7 -> [7]
8 -> [2, 2, 2]
9 -> [3, 3]
10 -> [2, 5]
11 -> [11]
12 -> [2, 2, 3]
13 -> [13]
14 -> [2, 7]
15 -> [3, 5]
16 -> [2, 2, 2, 2]
17 -> [17]
18 -> [2, 3, 3]
19 -> [19]
20 -> [2, 2, 5]
21 -> [3, 7]
22 -> [2, 11]
23 -> [23]
24 -> [2, 2, 2, 3]
25 -> [5, 5]
26 -> [2, 13]
27 -> [3, 3, 3]
28 -> [2, 2, 7]
29 -> [29]
30 -> [2, 3, 5]
```

</div></details>

<details><summary>計算量</summary><div>

TBD

</div></details>

<details><summary>参考リンク</summary><div>

TBD

</div></details>

### 最大公約数

<details><summary>説明</summary><div>

$1$ 以上の整数 $a$ と $b$ の最大公約数を返します。

</div></details>

<details><summary>ソースコード</summary><div>

```swift
private func gcd(_ a: Int, _ b: Int) -> Int {
    precondition(a > 0 && b >= 0)
    return b == 0 ? a : gcd(b, a % b)
}
```

</div></details>

<details><summary>出力例</summary><div>

```
gcd(2, 3) -> 1
gcd(6, 3) -> 3
gcd(24, 36) -> 12
```

</div></details>

<details><summary>計算量</summary><div>

$O(\log{N})$

$N$ は $a$ と $b$ のうち小さいほうの数値

</div></details>

<details><summary>参考リンク</summary><div>

- [ユークリッドの互除法 - Wikipedia](https://ja.wikipedia.org/wiki/ユークリッドの互除法)
- [提出 #162252 | アルゴ式](https://algo-method.com/submissions/162252)

</div></details>

### 最小公倍数

TBD

## おわりに

以上、 [Swift/Kotlin愛好会 Advent Calendar 2020](https://qiita.com/advent-calendar/2020/love_swift_kotlin) の6日目の記事でした。
明日も @uhooi の記事です。

## 参考リンク

- [uhooi/Programming-Swift-Solving: Solve competition programming using Swift.](https://github.com/uhooi/Programming-Swift-Solving)
- [Swift版 競プロ用チートシート(初心者向け) - Qiita](https://qiita.com/TARDIGRADE/items/71b0a774d7f22418fdf5)  
まずは自力で解きたいため、こちらの記事はまだほとんど参考にしていない