【実装コード有り】ElixirのMapSet(集合)の使い方と集合カバー問題を解くまで

Setは非推奨

元々、Elixirに実装されていたSetという集合のモジュールは現在、非推奨となっており
MapSetを使ってくれよなと公式が言っている

なのでよほどの理由がない限りはMapSetを使えばいいんじゃないかなと

MapSetの使い方

MapSetモジュールを使うことで集合を表現することが可能
集合はリストと異なり

同じデータを持つことができない

という特徴がある

lst = [1,1,2,3,4,4,5,6,7] #重複ok
set_ = [1,2,3,4,5,6,7] #重複は許可されない

新規集合の作成
MapSet.newメゾットを使うことで作成可能

iex> new_set = MapSet.new([1,2,3])
#MapSet<[1, 2, 3]>

#値の型は自由っぽい
iex> new_set = MapSet.new([:a, 1, false])
#MapSet<[1, :a, false]>

既存の集合への追加
MapSet.putメゾットを使う

new_set = MapSet.new([1,2,3])
iex> MapSet.put(new_set, 4)
#MapSet<[1, 2, 3, 4]>

集合同士の結合(和集合)
MapSet.unionメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,4,5])

iex> MapSet.union(a_set, b_set)
#MapSet<[1, 2, 3, 4, 5]>

集合同士の引き算(差集合)
MapSet.differenceメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,4,5])

#[1,2,3] - [2,4,5] ([4,5]はa_setに存在しないので影響なし)
iex> MapSet.difference(a_set, b_set)
#MapSet<[1, 3]>

両方の集合に含まれている要素を求める(積集合)
MapSet.intersectionメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,3, 4,5])

iex> MapSet.intersection(a_set, b_set)

集合の大きさの取得
MapSet.sizeメゾットを使う

a_set = MapSet.new([1,2,3])
iex> MapSet.size(a_set)
3

こいつで何ができるのか

一例として集合カバー問題というテーマに取り組む
これから以下の地域にそれぞれ野菜を届ける必要がある

#岐阜, 愛知, 三重, 京都, 静岡
delivery_regions = MapSet.new([:gihu, :aichi, :mie, :kyoto, :shizuoka])

現在、この地域に配達可能な業者が以下の5つ
それぞれの集合には配達可能な地域を記述してある

companies = %{
  neko: MapSet.new([:gihu, :mie, :shizuoka]),
  inu: MapSet.new([:mie, :kyoto]),
  saru: MapSet.new([:gihu, :kyoto, :aichi]),
  kani: MapSet.new([:mie, :aichi]),
  tori: MapSet.new([:aichi, :kyoto])
}

現状では全5地域に配達可能な企業がないため複数の企業に配達を依頼する必要がある
ではどの組み合わせを考えれば最も少ない企業数で配達が可能か
これが集合カバー問題といわれるものの一例です

Elixirでの実装

先にコードと実行結果をお見せします

defmodule Algo do
  def set_optimizer(delivery_regions, stations), do: _set_optimizer(delivery_regions, stations, MapSet.new())
  defp _set_optimizer(delivery_regions, stations, accum) do
    case delivery_regions == MapSet.new() do
      true -> accum
      false ->
        {best, states_coverted} = _set_update(delivery_regions, stations, Map.keys(stations), nil, MapSet.new())
        _set_optimizer(MapSet.difference(delivery_regions, states_coverted), stations, MapSet.put(accum, best))
    end
  end
  
  defp _set_update(_, _, [], best, accum), do: {best, accum}
  defp _set_update(need, stations, [head | tail], best, accum) do
    coverd = MapSet.intersection(need, stations[head])
    case MapSet.size(coverd) > MapSet.size(accum) do
      true -> _set_update(need, stations, tail, head, coverd)
      false -> _set_update(need, stations, tail, best, accum)
    end
  end
end

結果では:nekoと:saruの業者に頼むが良いと出ている
確かにそうだね

delivery_regions = MapSet.new([:gihu, :aichi, :mie, :kyoto, :shizuoka])
companies = %{
  neko: MapSet.new([:gihu, :mie, :shizuoka]),
  inu: MapSet.new([:mie, :kyoto]),
  saru: MapSet.new([:gihu, :kyoto, :aichi]),
  kani: MapSet.new([:mie, :aichi]),
  tori: MapSet.new([:aichi, :kyoto])
}
res = Algo.set_optimizer(delivery_regions, companies)
IO.inspect(res)
#result: #MapSet<[:neko, :saru]>

#全ての地域が含まれている
#:neko => [:gihu, :mie, :shizuoka]
#:saru => [:gihu, :kyoto, :aichi]

このモジュールは2つの再帰で動かしている
set_optimizerの関数で配達したい地域が全て満たされているかを判定させており
そうでない場合に再び再帰が行われる

set_optimizer

def set_optimizer(delivery_regions, stations), do: _set_optimizer(delivery_regions, stations, MapSet.new())
  defp _set_optimizer(delivery_regions, stations, accum) do
    #第1引数(配達したい地域)が空なら終了
    case delivery_regions == MapSet.new() do
      true -> accum
      false ->
        {best, states_coverted} = _set_update(delivery_regions, stations, Map.keys(stations), nil, MapSet.new())
        #_set_updateの結果を配達したい地域から引く
        _set_optimizer(MapSet.difference(delivery_regions, states_coverted), stations, MapSet.put(accum, best))
    end
end

_set_update

defp _set_update(_, _, [], best, accum), do: {best, accum} #companiesの列挙が終わった時に終了
defp _set_update(need, stations, [head | tail], best, accum) do
  #accum(1つ前の値)との差分をみる
  coverd = MapSet.intersection(need, stations[head])
  case MapSet.size(coverd) > MapSet.size(accum) do
    true -> _set_update(need, stations, tail, head, coverd) #頼む業者を更新&配達可能地域を保持
    false -> _set_update(need, stations, tail, best, accum) #更新なし
  end
end