弾です。ちょっと野暮用で必要になったので 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