ランダムランチの組み合わせアルゴリズムを考えて実装した

この記事は Livesense - 自 Advent Calendar 2017 4日目の記事です。
テーマ「関」というわけで、組織内で関係を作るためのランダムランチについて書きます。

ランダムランチとは？

社内交流の取り組みの一つで、社員をランダムなグループを作ってランチに行くというイベントです。シャッフルランチという呼び方もされるようです。
組織が大きくなってくると、全く話さない部署の人が出て来るものです。また、いつも同じメンバーでランチに行っていると安心感はあるのですがマンネリ化もします。
ランダムランチをすることで離れた部署のメンバーと交流ができ、これが社内の弱い紐帯を育むのです。素晴らしい！

弊社でもランダムランチを行うときがあります。
全社員職種問わずであったり、エンジニアの有志（ほぼ全員が参加）であったり、部署の一部メンバーで行ったり、その時々です。

そこで難しいのは組み合わせです。
数回繰り返した時に過去の開催結果を考慮しなくてはいけない、かつ、その組み合わせで良いという明確な答えが無いため、手動でやると頭が爆発しそうになります。
単純にランダムでグループを作ると、よく話す同じチームの人であったり、前回のランダムランチで一緒だった人とまた同じグループになってしまいます。

こんなときこそコンピュータの力を使って自動化しましょう！

gemを作りました

私のプログラミングにおける母国語はRubyであるためgemにしました。
GroupMixerと名付けました。
計算量は参加者数の2乗になります。
数万の組織でランダムランチをすることは無いと思うので、とりあえず大丈夫だと思います。

以下、その解説となります。

問題を定義する

どのようにグループを分ければ良いか。要求としては以下のようになります。

• できるだけ普段交流が無い人と組み合わせる。
• できるだけ過去に一緒になった人は組み合わせない。
• それなりにランダム。

できるだけ、というのがポイントで２０人ぐらいの組織で毎週やればそのうち同じ人に当たるのは必然だからです。

既存のアルゴリズムを探してみる

逆、つまりクラスタリングにはいくつも定番アルゴリズムがあります。
今回の問題は、全体ができるだけ離れた人の組み合わせになるように分けなくてはいけません。
（クラスタリングして分かれた各組から一人ずつランダムに選ぶ、という方法でもそれなりにいけそうだなと書いていて思いつきました）

昔からやってみたかった巡回セールスマン問題などを解くのに使われる蟻コロニー最適化も良いかなと思ったのですが、実装が面倒で採用しませんでした。

今回作成したアルゴリズム

アルゴリズムと呼ぶにはおこがましいぐらいですが、ぱっと思いついたのは以下のような手順です。

1. 過去のランダムランチの組み合わせや所属している組織などから、個々人の関連度を出す
   1. 関連度とは関わった人の数と考えてください
   2. 多くの組織に所属したことがあったり、社内で顔の広い人は大きな関連度を持つことになります
   3. 逆に新しく入社した人は関連度は少なくなります
2. 関連度が大きい人から、グループに割り当てていく
3. 割り当てられるグループは以下のように選ぶ
   1. 割り当てられる時点で、最も関連度の合計が低くなるグループ
   2. 最も関連度の合計が低くなるグループが複数ある場合、最も人数の多いグループ
   3. 上記２つの条件を満たすグループが複数ある場合は、その中からランダムに選ぶ

2の順番でメンバーを割り当てることの意味は、関連度の小さい人を後で配置したほうが全体の関連度を下げられるからです。
（今日会社に入ったばかりの新メンバーはどのグループに配置しても関連度は０）
3の2で最も人数の多いグループを選ぶのは、関連度が大きい人をまとめておいたほうが後から配置される人との関連度を下げられるからです。

厳密な意味で最適な解では無いですが、これでそこそこの結果が得られると思います。

今後の展望

現状だと少なくともRubyを触れる人にしか使えないので、Webサービス化も検討しております。
すでにそれっぽいツールもあるようですが、理想としては調整さんのように登録せずともやりやすいサービスにしてみたいです。

更に機能として検討しているのは、

• 初回データを作る方法（参加者が入れられるようにする、など）
• 参加者を入力する、または募集する画面
• なんらかの方法で組み合わせの良さを数値化して表示
• ある人とある人を絶対同じグループに入れる
• ある人とある人を絶対に同じグループに入れない

みたいな感じです。