Pythonで行列の全行に共通する要素を効率的に見つける方法

問題の概要

m × m の正方行列が与えられたとき、すべての行に共通して現れる重複しない要素をすべて抽出することを考えます。

たとえば、次のような入力が与えられたとしましょう。

この場合、すべての行に共通して含まれる要素は 2、4、15 の3つであるため、出力は [2, 4, 15] となります。

解決のためのアプローチ

この問題は、マージソートの「マージ処理」に似た発想で効率的に解くことができます。ポイントは、各行をあらかじめソートしておき、ポインタを進めながら共通要素を探すことです。具体的な手順は以下の通りです。

手順1：sortRows() 関数を定義する

引数として行列 matrix を受け取ります。n を行数とし、i を 0 から n-1 までループしながら、matrix[i] の各行を昇順にソートします。

手順2：メイン処理を実装する

• n := 行数とし、sortRows(matrix) を呼び出して全行をソートします。
• current_idx := 各行の走査位置を記録するサイズ n のリスト。すべて 0 で初期化します。
• f := 0（探索終了を示すフラグ）。
• current_idx[0] < n の間、以下を繰り返します。
  • value := matrix[0][current_idx[0]] … 1行目から候補となる値を取り出します。
  • present := True で初期化します。
  • i を 1 から n-1 までループします。
    • current_idx[i] < n かつ matrix[i][current_idx[i]] <= value の間、current_idx[i] を1ずつ増やします。
    • matrix[i][current_idx[i] - 1] が value と等しくなければ、present := False とします。
    • current_idx[i] が n に達したら、それ以上共通要素は存在しないため f := 1 として内側のループを抜けます。
  • present が True のままなら、value は全行に共通する要素なので出力します。
  • f == 1 なら外側のループも終了します。
  • current_idx[0] を1増やして、次の候補値へ進みます。

実装例

それでは、実際のPythonコードで動作を確認してみましょう。

MAX = 100

def sortRows(matrix):
    n = len(matrix)
    for i in range(0, n):
        matrix[i].sort()

def find_common(matrix):
    n = len(matrix)
    sortRows(matrix)
    current_idx = [0] * n
    for i in range(0, n):
        current_idx[i] = 0
    f = 0
    while(current_idx[0] < n):
        value = matrix[0][current_idx[0]]
        present = True
        for i in range(1, n):
            while (current_idx[i] < n and matrix[i][current_idx[i]] <= value):
                current_idx[i] = current_idx[i] + 1
            if (matrix[i][current_idx[i] - 1] != value):
                present = False
            if (current_idx[i] == n):
                f = 1
                break
        if (present):
            print(value, end = ", ")
        if (f == 1):
            break
        current_idx[0] = current_idx[0] + 1

mat = [
    [13, 2, 15, 4, 17],
    [15, 3, 2, 4, 36],
    [15, 2, 15, 4, 12],
    [15, 26, 4, 3, 2],
    [2, 19, 4, 22, 15]]
find_common(mat)

入力

[[13, 2, 15, 4, 17],
[15, 3, 2, 4, 36],
[15, 2, 15, 4, 12],
[15, 26, 4, 3, 2],
[2, 19, 4, 22, 15]]

出力

2, 4, 15,

アルゴリズムのポイントと計算量

この手法の強みは、各行を事前にソートしておくことで、共通要素の判定をポインタの前進だけで完結できる点にあります。また、ある行の走査位置が末尾（n）に達した時点で共通要素はもう存在しないため、無駄な比較を行わずに即座に探索を打ち切れるのも特徴です。

計算量を見てみると、全行のソートに O(n² log n)、共通要素の走査に O(n²) が必要となり、全体で O(n² log n) 程度になります。すべての要素を総当たりで比較する非効率な手法よりも高速に動作します。

なお、Pythonでは set を活用して set(mat[0]) & set(mat[1]) & ... のように積集合を求めることでも同じ結果が得られます。ただし、本記事で紹介したソート＋ポインタ走査の手法は、メモリ使用量を抑えつつ大規模なデータにも応用できる古典的かつ有用なアプローチです。