弾です。ちょっと野暮用で必要になったので Swift で combinatorics (組合せ数学)を扱うモジュールを書いたので公開します。
ざっくりjs-combinatoricsのSwift版ですが、Swiftだけあって
-
.nth()
などというなんちゃってではない本物のsubscript
が使える - 配列のみならず
Sequence
を受け付けるので直接0..<16
や"string"
を食わせられる(ただし結果は.map()
などと同様配列)。 -
Sequence
に準拠しているので.map()
や.filter()
を再発明せずにすんでいる。 -
subscript
の添字がInt
決め打ちではなくSignedInteger
を受け付けるようにしてあるのでBigIntなどと組み合わせて「要素数100個のSequence
の最後の順列」を取り出すことも可能。
import Combinatorics
for chars in Permutation(of:"swift") {
print(String(chars)) // アナグラム
}
インストールの方法はいつも通り。他モジュールの依存はありません。が前述の通りBigIntなどの非標準なSignedInteger
と組み合わせる場合には別途それが必要になります(後述)
イテレーター
本モジュールに付属するstruct
はいずれも本のSequence
から[n]
でn
番目の要素を返すランダムアクセス可能なSequence
を生成します。
Permutation
- 順列
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
- 組み合わせ
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
)を数字に見立てた数値
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
- 冪集合
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
- 直積
直積に関してはtupleを返すCartesianProduct
と配列を返すProductSet
の二種類を用意してあります。
CartesianProduct
は2つのCollection
の直積を返します。要素の型は異なっていても構いません。
let suits = "♠️♦️❤️♣️"
let ranks = 1..13
let cp = CartesianProduct(suits, ranks)
cp.count // 52
cp.map { $0 } //[("♠️",1)...("♣️",13)]
またそれ自身もCollection
なので、以下のようにして直積の直積も導出できます。
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
として別途用意しました。
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とかでもいけます。
// 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
のイテレーターは、内部的には以下の通り定義されています。
public typealias Permutation = CombinatoricsIndex<Int>.Permutation
public typealias Combination = CombinatoricsIndex<Int>.Combination
// …
public typealias ProductSet = CombinatoricsIndex<Int>.ProductSet
CombinatoricsIndex<Index:SignedInteger>
でwrapすることで添字の型を切り替えているのですが、だとしたらBigPermutation
は以下のようにして定義できることになります。
typealias BigPermutation = CombinatoricsIndex<BigInt>.Permutation
実際その通りで、参考パッケージがBigCombinatorics
として同封されているのでご覧ください。ただしイテレートしたら組合せ爆発に巻き込まれるという点はご留意を。
さいごに
js-combinatoricsの⭐️の数から見るに、組合せ数学は実装がコンパクトなわりに難しいというのが透けてみえます。実際総称型もプロトコルもないECMAScriptでやるのは結構大変でした。車輪を再発明したくない型、もとい方はぜひご利用ください。
Dan the Safe, Fast, and Expressive