Swift - introducing swift-combinatorics

弾です。ちょっと野暮用で必要になったので Swift で combinatorics (組合せ数学)を扱うモジュールを書いたので公開します。

* https://github.com/dankogai/swift-combinatorics

ざっくり[js-combinatorics]のSwift版ですが、Swiftだけあって

[js-combinatorics]:https://github.com/dankogai/js-combinatorics

* `.nth()`などというなんちゃってではない本物の`subscript`が使える
* 配列のみならず`Sequence`を受け付けるので直接`0..<16`や`"string"`を食わせられる(ただし結果は`.map()`などと同様配列)。
* `Sequence`に準拠しているので`.map()`や`.filter()`を再発明せずにすんでいる。
* `subscript`の添字が`Int`決め打ちではなく`SignedInteger`を受け付けるようにしてあるので[BigInt]などと組み合わせて「要素数100個の`Sequence`の最後の順列」を取り出すことも可能。

[BigInt]: https://github.com/attaswift/BigInt

```swift
import Combinatorics

for chars in Permutation(of:"swift") {
    print(String(chars)) // アナグラム
}
```

インストールの方法はいつも通り。他モジュールの依存はありません。が前述の通り[BigInt]などの非標準な`SignedInteger`と組み合わせる場合には別途それが必要になります(後述)

## イテレーター

本モジュールに付属する`struct`はいずれも本の`Sequence`から`[n]`で`n`番目の要素を返すランダムアクセス可能な`Sequence`を生成します。

### `Permutation` - [順列]

[順列]: https://ja.wikipedia.org/wiki/%E9%A0%86%E5%88%97

```swift
var p = Permutation(of:"abcd")
p.count      // 24
p[p.count-1] // ["d","c","b","a"]
p.map { $0 } // [["a","b","c","d"]...["d","c","b","a"]]
p = Permutation(of:"abcd", size:2)
p.count      // 12
p[p.count-1] // ["d", "c"]
p.map { $0 } // [["a","b"] ... ["d","c"]]
```

### `Combination` - [組み合わせ]

[組み合わせ]: https://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B_(%E6%95%B0%E5%AD%A6)

```swift
var c = Combination(of:"abcd")
c.count      // 1
c[c.count-1] // ["a","b","c","d"]
c.map { $0 } // [["a","b","c","d"]]
c = Combination(of:"abcd", size:2)
c.count      // 6
c[c.count-1] // ["c","d"]
c.map { $0 } // [["a","b"],["a","c"],["a","d"],["b","c"], ["b","d"], ["c","d"]]
```

### `BaseN` - 本`Sequence`の要素(`Element`)を数字に見立てた数値

```swift
var d = BaseN(of:0...3)
d.count      // 4 ** 4 == 256
d[d.count-1] // [3,3,3,3]
d.map { $0 } // [[0,0,0,0]...[3,3,3,3]]
d = BaseN(of:0...3, size:2)
d.count      // 16
d[d.count-1] // [3,3]
d.map { $0 } // [[0,0]...[3,3]]
```

### `PowerSet` - [冪集合]

[冪集合]: https://ja.wikipedia.org/wiki/%E5%86%AA%E9%9B%86%E5%90%88

```swift
let s = PowerSet(of:0...3)
s.count      // 2 ** 4 == 16
s[s.count-1] // [0,1,2,3]
s.map { $0 } // [[],[0],[1],[0,1]...[0,1,2,3]]
```

### `CartesianProduct` と `ProductSet` - [直積]

[直積]: https://ja.wikipedia.org/wiki/%E7%9B%B4%E7%A9%8D%E9%9B%86%E5%90%88

直積に関してはtupleを返す`CartesianProduct`と配列を返す`ProductSet`の二種類を用意してあります。

`CartesianProduct`は2つの`Collection`の直積を返します。要素の型は異なっていても構いません。

```swift
let suits = "♠️♦️❤️♣️"
let ranks =  1..13
let cp = CartesianProduct(suits, ranks)
cp.count // 52
cp.map { $0 } //[("♠️",1)...("♣️",13)]
```

またそれ自身も`Collection`なので、以下のようにして直積の直積も導出できます。

```swift
let cp = CartesianProduct("01", "abc")
let cpcp = CartesianProduct(cp, "ATCG")
cp.count // 24
cpcp.map{ $0 } // [(("0","a"),"A")...(("1","c"),"G")]
```

直積の定義からするとtupleが正しいのですが、多次元のtupleというのは非常に扱いづらく、よって全ての要素の型が共通していることと引き換えに多次元の直積をまとめて導出できるバージョンを`ProductSet`として別途用意しました。

```swift
let ps = ProductSet([0,1],[2,4,6],[3,6,9,12],[4,8,12,16,20])
ps.count // 2 * 3 * 4 * 5 == 120
ps.map{ $0 } // [[0, 2, 3, 4] ... [1, 6, 12, 20]]
````

## 演算関数

以下のユーティリティー用関数も型関数(static functions)として用意してあります。いずれも`SignedInteger`を引数として受け付けるので[BigInt]とかでもいけます。

```swift
// T:SignedInteger
Combinatorics.factorial<T>(_ n:T)->T
Combinatorics.permutation<T>(_ n:T, _ k:T)->T
Combinatorics.combination<T>(_ n:T, _ k:T)->T
```

## `Int`以外の添字を使うには

`Combinatorics`のイテレーターは、内部的には以下の通り定義されています。

```swift
public typealias Permutation        = CombinatoricsIndex<Int>.Permutation
public typealias Combination        = CombinatoricsIndex<Int>.Combination
// …
public typealias ProductSet         = CombinatoricsIndex<Int>.ProductSet
```

`CombinatoricsIndex<Index:SignedInteger>`でwrapすることで添字の型を切り替えているのですが、だとしたら`BigPermutation`は以下のようにして定義できることになります。

```swift
typealias BigPermutation        = CombinatoricsIndex<BigInt>.Permutation
```

実際その通りで、参考パッケージが`BigCombinatorics`として同封されているのでご覧ください。ただしイテレートしたら組合せ爆発に巻き込まれるという点はご留意を。

## さいごに

[js-combinatorics]の⭐️の数から見るに、組合せ数学は実装がコンパクトなわりに難しいというのが透けてみえます。実際総称型もプロトコルもないECMAScriptでやるのは結構大変でした。車輪を再発明したくない型、もとい方はぜひご利用ください。

Dan the Safe, Fast, and Expressive