Juliaで集合を同値類に分割する

Juliaでは縦ベクトルをA = [1,2,3,4,5]のように定義でき, 集合はA = Set([1,2,3,4,5])のように定義できます. 今回はインデックスに頼らないと実装が回りくどくなりますので, 縦ベクトルを集合の代わりに使っていきます.

集合の具体例

先ほど説明した例

julia> A = [1,2,3,4,5]

を同値類に分割していきます.

同値関係の具体例

偶数同士か奇数同士のどちらかならtrue, そうでなければfalseを返すような同値関係f(i,j)をうまく定義しましょう. Juliaでは与えられた整数が奇数か否かをiseven()やisodd()で判定できるので, この結果が等しいか否か判定するだけです.

julia> f(i,j) = iseven(i) == iseven(j)

julia> f(1,2)
false

julia> f(1,3)
true

julia> f(1,4)
false

julia> f(2,2)
true

julia> f(2,4)
true

このような2変数のBool値関数を使って, 集合を同値類に分割します.

分割する方法

集合Sと同値関係Rを入力として, 同値類の集合classesと代表元の集合representativesを出力するような関数を考えました.

function classify(S, R)
    classes = []
    representatives = [] 
    for x ∈ S
        i = findfirst([R(x,y) for y ∈ representatives])
        if isnothing(i)
            push!(classes, [x])
            push!(representatives, x)
        else
            push!(classes[i], x)
        end
    end
    return classes, representatives
end

findfirst()の内部でブロードキャスト用いることもできますが, 個人的に想定している状況だとエラーが出るため避けました. それでは試してみましょう.

julia> classify(A, f)
([[1, 3, 5], [2, 4]], [1, 2])

うまくいきました. 商集合[[1, 3, 5], [2, 4]]と代表元の集合[1, 2]を出力してくれています.

おわりに

A = [1,2,3,4,5]を奇数と偶数に分ける例を考えました. それらしいパッケージが見当たらなかったためスクラッチしましたが, 既にあってもおかしくないと思うので, 何かご存じの方は情報を共有して頂けますと幸いです.