注目キーワード
  1. Youtube
  2. 360VR
  3. Vegas Pro

グループ化アルゴリズム

  • 2020年3月31日
  • 2021年10月11日
  • 備忘録
  • 17回
  • 0件

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

スポンサーリンク_123

やりたかったこと

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

グループ化のイメージ

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

計算条件

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

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

アルゴリズムの考えかた

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

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

スポンサーリンク_4