日記や趣味、学んだことを忘れないようにして記録するサイト

mz8k

日記

グループ化アルゴリズム

更新日:

2:スポンサーリンク

すみません、正しい言い方が分かりません。ググったら「素集合データ構造」や「同値類の分類」や「同値関係」と言うらしいけど思いっきり間違っているかもしれません。

やりたかったこと

 仕事上でやりたかった事、解析したかったことを書きます。簡単に言うと「友達友達はみな友達だ。世界に広げよう、友達の輪!」ので「輪」の数を見つけるアルゴリズムを考えてみた。
 もっと簡単に言うと「Aさん と Bさんはお友達」、「 Cさん と Dさんはお友達 」、更に「 Bさん と Cさんはお友達 」だから「Aさん Bさん Cさん Dさんは、みんなお友達」(実際には Aさん Dさん は知らない人同士だけど・・)ABCDさんの、「ともだちグループA(仮称)」としたときに、数千人とか数万人いる人々たちをグループ化するアルゴリズムを考えて見た。
 まあ、これって合コンのグルーピングに似ていますね。たぶんFaceBookも基本は同じような考えだと思いますが、もっと高度な判定をしているんでしょうね。

グループ化のイメージ

 まあ、これは一例ですが・・・。仕事上問題解決しなければならないのは、このような条件を持つ個々の集まりが何万近く存在し、上記の”ともだちグループ”が何通りできるのか?を調べる必要があったのです。
 ひょっとしたら何万人いても結局1グループで収まるのか?、または友達が少なすぎて結局は何万というグループに分かれるのか? さて、あなたならどうやってグルーピング化を計算しますか?

1:スポンサーリンク

計算条件

実際の世界では考えられない感じもしますが、グルーピング化の条件は以下のとおり

  • 友達の条件としては「東京小学校」=「山田一郎」、「埼玉大学」=「田中一郎」、「東京小学校」=「高橋一郎」、「東京小学校」=「鈴木一郎」の様に変数で条件付けする。この場合は右辺は名前(「山田一郎」、「田中一郎」、「高橋一郎」、「鈴木一郎」)、左辺は出会いの条件の関係で同じ条件同士ではお友達とする(「山田一郎」、「高橋一郎」が友達)
  • 友達グループが何人いても、1人でもお友達がいれば同一グループとする。(お友達グループAに何万人居ようが、お友達グループBに何万人居ようが、お友達グループA・Bに一人でも共通する友達が各々居たら1つのグループとなる。結構シュールな条件ですが、プログラム上の考えです)
出会の条件氏名
東京小学校山田一郎
埼玉大学田中一郎
東京小学校高橋一郎
神奈川高校鈴木一郎
条件のデータイメージ

1:スポンサーリンク

アルゴリズムの考えかた

どちらかを基準にして配列を作る

最終的な結果は「山田一郎」Aグループ、「田中一郎」Bグループ、「高橋一郎」Aグループ、「鈴木一郎」Cグループ・・というように分けられれば、あとは名前をキーとして”出会の条件”が引けますし、引いてきた”出会の条件”から別の名前も引けますので、名前の配列を作ります。

3:スポンサーリンク

-日記

Copyright© mz8k , 2021 All Rights Reserved Powered by STINGER.