post Image
Swift – introducing swift-combinatorics

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

CartesianProductProductSet直積

直積に関しては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


『 Swift 』Article List
Category List

Eye Catch Image
Read More

Androidに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

AWSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Bitcoinに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

CentOSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

dockerに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

GitHubに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Goに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Javaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

JavaScriptに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Laravelに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Pythonに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Rubyに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Scalaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Swiftに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Unityに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Vue.jsに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Wordpressに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

機械学習に関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。