Pythonで連絡先リストから同一人物の連絡先を検索する方法

問題の概要

ユーザー名、メールアドレス、電話番号を任意の順序で保持する連絡先のリストがあるとします。このリストの中から「同一人物」に紐づく連絡先(同じ人が複数の異なる連絡先情報を持っているケース)を見つけ出し、同一の連絡先どうしをまとめて返すことを考えます。

この問題を解くうえで、次の2つのポイントを押さえておく必要があります。

• 各連絡先は、ユーザー名・メールアドレス・電話番号という3つのフィールドを、どのような順序で格納していても構いません。
• 2つの連絡先は、ユーザー名・メールアドレス・電話番号のいずれか1つでも一致していれば「同じ」とみなすものとします。

たとえば、入力が以下のような場合を考えてみましょう。

Contacts = [{"Amal", "amal@gmail.com", "+915264"},
            {"Bimal", "bimal321@yahoo.com", "+1234567"},
            {"Amal123", "+1234567", "amal_new@gmail.com"},
            {"AmalAnother", "+962547", "amal_new@gmail.com"}]

この場合の出力は [0, 2, 3] と [1] になります。インデックス 0・2・3 の連絡先は電話番号やメールアドレスを共有しているため同一人物と判断され、インデックス 1 の連絡先は他と一致する項目がないため独立したグループとなります。

解決のアプローチ

この問題は、「連絡先同士の一致関係をグラフ(隣接行列)として表現し、連結成分ごとにグループ化する」という発想で解けます。全体の流れは次のとおりです。

1. 各連絡先を頂点とみなし、何らかのフィールドが一致する連絡先同士を辺で結んだ隣接行列を作成する(generate_graph())。
2. DFS(深さ優先探索)を使って隣接行列をたどり、つながっている連絡先を同じグループとして抽出する(visit_using_dfs())。

アルゴリズムの手順

手順1:generate_graph() の定義(引数は cnt、n、matrix)

• i を 0 から n-1 まで、j を 0 から n-1 までループさせ、matrix[i][j] = 0 で初期化します。
• 続いて i を 0 から n-1 まで、j を i+1 から n-1 までループさせます。
• cnt[i] と cnt[j] のスロット(slot1〜slot3)を総当たりで比較し、1つでも一致する組み合わせがあれば、matrix[i][j] と matrix[j][i] を 1 に設定してループを抜けます。

手順2:visit_using_dfs() の定義(引数は i、matrix、visited、sol、n)

• visited[i] = True として訪問済みマークを付けます。
• インデックス i を結果リスト sol の末尾に追加します。
• j を 0 から n-1 までループし、matrix[i][j] が非ゼロ(つまり連絡先 j とつながっている)かつ j が未訪問であれば、再帰的に visit_using_dfs(j, ...) を呼び出します。

手順3:メインメソッドでの処理

• n := 連絡先リスト cnt の要素数
• sol := 新しい空のリスト
• matrix := n × n の正方行列を作成
• visited := 長さ n の配列を作成し、すべて 0 で初期化
• generate_graph(cnt, n, matrix) を呼び出してグラフを構築
• i を 0 から n-1 までループし、未訪問の i に対して visit_using_dfs(i, matrix, visited, sol, n) を実行した後、sol の末尾に区切り文字として -1 を追加
• 最後に sol を走査し、値が -1 の場合は改行を出力、それ以外の場合はそのインデックスを表示

実装例

それでは、実際のコードを見てみましょう。

class contact:
    def __init__(self, slot1, slot2, slot3):
        self.slot1 = slot1
        self.slot2 = slot2
        self.slot3 = slot3

def generate_graph(cnt, n, matrix):
    for i in range(n):
        for j in range(n):
            matrix[i][j] = 0
    for i in range(n):
        for j in range(i + 1, n):
            if (cnt[i].slot1 == cnt[j].slot1 or cnt[i].slot1 == cnt[j].slot2 or cnt[i].slot1 == cnt[j].slot3 or cnt[i].slot2 == cnt[j].slot1 or cnt[i].slot2 == cnt[j].slot2 or cnt[i].slot2 == cnt[j].slot3 or cnt[i].slot3 == cnt[j].slot1 or cnt[i].slot3 == cnt[j].slot2 or cnt[i].slot3 == cnt[j].slot3):
                matrix[i][j] = 1
                matrix[j][i] = 1
                break

def visit_using_dfs(i, matrix, visited, sol, n):
    visited[i] = True
    sol.append(i)
    for j in range(n):
        if (matrix[i][j] and not visited[j]):
            visit_using_dfs(j, matrix, visited, sol, n)

def get_similar_contacts(cnt):
    n = len(cnt)
    sol = []
    matrix = [[None] * n for i in range(n)]
    visited = [0] * n
    generate_graph(cnt, n, matrix)
    for i in range(n):
        if (not visited[i]):
            visit_using_dfs(i, matrix, visited, sol, n)
            sol.append(-1)
    for i in range(len(sol)):
        if (sol[i] == -1):
            print()
        else:
            print(sol[i], end = " ")

cnt = [contact("Amal", "amal@gmail.com", "+915264"),
       contact("Bimal", "bimal321@yahoo.com", "+1234567"),
       contact("Amal123", "+915264", "amal_new@gmail.com"),
       contact("AmalAnother", "+962547", "amal_new@gmail.com")]
get_similar_contacts(cnt)

入力

cnt = [contact("Amal", "amal@gmail.com", "+915264"),
contact("Bimal", "bimal321@yahoo.com", "+1234567"),
contact("Amal123", "+915264", "amal_new@gmail.com"),
contact("AmalAnother", "+962547", "amal_new@gmail.com")]

出力

0 2 3
1

処理の流れを確認しよう

この入力では、インデックス 0 の連絡先(Amal)とインデックス 2 の連絡先(Amal123)は電話番号 +915264 が一致しており、さらにインデックス 2 とインデックス 3(AmalAnother)はメールアドレス amal_new@gmail.com が一致しています。そのため、0 → 2 → 3 とつながった1つのグループとして検出され、最初の行に「0 2 3」と出力されます。一方、インデックス 1(Bimal)はどの連絡先とも一致する項目がないため、独立したグループとして2行目に「1」と表示されるわけです。

なお、この実装では連絡先のペアごとに全フィールドを比較しているため、計算量は O(n²) となります。連絡先の件数が非常に多い場合は、Union-Find(素集合データ構造)やハッシュマップを使った手法に置き換えることで、より効率的に処理できる点も覚えておくとよいでしょう。