やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵

トップ > Algorithm > クリスマスプレゼントの交換会にElixirで備える

クリスマスプレゼントの交換会にElixirで備える

Algorithm Elixir

今年で24歳になりましたが、いつになってもクリスマスってのはワクワクしますね。山下達郎さんのクリスマスイブを耳にすると「もう12月かぁ〜」と胸が苦しくなります。
そんなこんなで友人とクリスマスプレゼントの交換会をすることになりました(唐突)。
誰が誰にプレゼントを送るかという決定に忖度がないように、プレゼント交換のペアを自動で出力できるようなプログラムを組みました。

f:id:takamizawa46:20201114133430p:plain これは完全に『遊び』です。

【超絶技巧】CARAVAN／村下孝蔵 - ニコニコ動画

実装方針について

案1: ピポットとランダムな選択

どんなデータ構造を使えば効率よく、ペアを組めるのかを考えてみました。最初に素直に参加メンバーの名簿をリストで用意してみます。実際には3人でやるんですが、見栄えをよくするために6人ぐらいにしておきます。

member = ["tomoya", "nagisa", "kyou",  "ryou", "tomoyo", "kotomi"]

簡単に考えると、リストの先頭要素(ピポット)を取得して、プレゼントを送る側としてfixします。それに対応するプレゼントを受け取る側は先頭要素以外のメンバーの配列から一人を無作為に選ぶことで決定することが出来そうです。簡単にコードに落としてみます。

defmodule SecretSanta do
    def create_pair([_ | []]), do: :ok
    def create_pair([h | t]) do
        IO.puts("#{h} => #{Enum.random(t)}")
        create_pair(t)
    end
end

member = ["tomoya", "nagisa", "kyou",  "ryou", "tomoyo", "kotomi"]
SecretSanta.create_pair(member)

再帰処理を用いて、上記の処理を完成させてあります。ランダムで受け取るメンバーを選択しているので実行ごとに結果が変わりますが、一例として結果を以下に記します。

tomoya => nagisa
nagisa => ryou
kyou => tomoyo
ryou => kotomi
tomoyo => kotomi

一見、良い感じにペアが決まっているように見えますが問題が潜在しています。プレゼントを送る側は重複することはありませんが、プレゼントを受け取る側はtailから無作為に選択されるので、重複する可能性があります。特にtailの要素数が少なくなれば少なくなるほど、その確率は高まります。

回避策として、誰がすでにペアとなっているか(選択されているか)を記録してあげれば重複が出ない様になるかと思いますが、その管理をするのが面倒です。ですので、こちらの案は一旦、保留としておきます。

案2 : グラフ構造を用いる

色々調べていたところ、この問題は既出の有名な問題であり、「Secret-Santa-Problem」というものだそうです。論文やらアルゴリズムの解説がいくつかありました。参考文献に貼っておきます。

概要を説明すると巡回グラフ構造を用いて、StartからEndまでの道を求めることで、プレゼント交換のペアが決定されるとのことです。次のグラフ(地点)の選択は最も簡単な方法であればランダム選択をするようです。応用として、Aさんがお金持ちであった場合、Bさんが貧相であった場合に重みを付与することで、忖度を表現することが出来そうですね。

とはいえ、今回の実装としてはリッチすぎるので、一旦保留としておきましょう。

案3: メンバーをランダムにシャッフル

グラフ構造を使うという発想を得てから、「こうすればいいんじゃないかね」と思い付いた方法です。案1ではプレゼントを送る人が重複してしまうため、選択されたメンバーを記録しておく必要がありそうでした。しかしながら面倒です。
データの列挙がイコール、応募者のペアとなっているのが最も楽です。それがグラフ構造でA->B->CというのはA->B, B->C, C->Aというペアを表しています。これをリストで表現できたら楽だなぁと思いました。

ランダムで選択されるという処理が面倒なので、事前にメンバーの一覧のリストをシャッフルしておけば、再帰処理で取得されるピポットがランダムで選択された一人だと同等だと考えることが出来そうです。まとめると以下の手順で処理を行います。

  • メンバーを記録しているリストをシャッフルする
  • シャッフルした配列に対して再帰処理を実行。headとtailを取得する
  • headをプレゼントを送る側、tailの先頭要素をプレゼントを受け取る側とする
  • tailが空(残りのメンバーがいない)の場合に、最初の一人をプレゼントを受け取る側とする

この方法が良さそうですので、採用してコードに落としてみます。

実装

先にコードを載せておきます。最近、ミニマムなコードはgistを使って管理しています。本当に便利。

gist.github.com

処理として面倒なのはtailが空(残りのメンバーがいない)の場合に、最初の一人をプレゼントを受け取る側とするという箇所でしょう。どうしたものかと悩みましたが、逆に考えると最初の一人だけを記録しておけば良いので、アキュムレーターとして最初の一人を記録させるようにしました。

defp print_result([h | _] = lst), do: _print_result(lst, h)
defp _print_result([h | []], first) do
  template_print(h, first)
  _print_result([], first)
end

引数パターンマッチングのおかげで、条件一致させるのも楽ですね。リストの中のリストでさえも簡単に条件を拾えます。処理は可能な限り関数として分散させています。同名関数が定義可能なのは命名に困らないので非常に助かります。

実行結果

最後に結果を出力しておきます。

ryou => tomoyo
tomoyo => kotomi
kotomi => nagisa
nagisa => kyou
kyou => tomoya
tomoya => ryou

グラフ構造を用いた案2のStart->Endの関係をリストでも表現することが出来ました。これでプレゼント交換のペア決めはばっちりですね。

おまけ

パフォーマンスの視点で考えるとEnum.shuffleがどれだけの計算量なのかが気になります。データのシャッフルとして有名なのはFisher-Yates shuffleというものがあるそうです。配列から要素をランダムに1つ選択して、それを末尾の要素と入れ替える処理を繰り返すことで配列をシャッフルします。計算量はO(n)で、非常にパフォーマンスが良いですね。

問題はElixirでこのFisher-Yates shuffleが実装されているのかということです。Elixirのenum.exにsfuffleの実装がありました。

@spec shuffle(t) :: list
def shuffle(enumerable) do
  randomized =
    reduce(enumerable, [], fn x, acc ->
      [{:rand.uniform(), x} | acc]
    end)

  shuffle_unwrap(:lists.keysort(1, randomized), [])
end

Elxiirでランダム値を先頭要素に持つタプルを作成して、erlangの:lists.keysortという関数を用いて、ソートをしています。
mike-neck.github.io

なので乱数生成 + ソートを用いて配列をシャッフルしているということになります。これ以上、コードの追従はしませんが、ソートの計算量は多くてもセレクトソートのO(n^2)程度だと考えられるので、重荷になるような処理ではないかと思います。

参考文献