【Python】行列の異なる行から指定した合計になるペアをすべて検索する方法

問題の概要

ユニークな要素で構成される行列（マトリックス）と目標の合計値が与えられたとき、合計がその値と一致するすべてのペアを行列から見つけます。ただし、ペアを構成する2つの要素は、必ず異なる行から取得する必要があります。

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

sum = 13 の場合、出力は次のようになります。

[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]

アルゴリズムの手順

この問題は、各行をあらかじめソートしておき、行の組み合わせごとにツーポインター法を用いて合計が一致するペアを効率よく探索します。手順は以下の通りです。

1. 結果を格納するための空リスト res を用意します。
2. n := 行列のサイズとします。
3. i を 0 から n-1 まで繰り返し、各行 matrix[i] を昇順にソートします。
4. i を 0 から n-2 まで、j を i+1 から n-1 まで繰り返します。
   • low := 0、high := n - 1 でポインターを初期化します。
   • low < n かつ high >= 0 の間、以下を繰り返します。
     • matrix[i][low] + matrix[j][high] が sum と等しい場合：(matrix[i][low], matrix[j][high]) を res に追加し、low を +1、high を -1 します。
     • 合計が sum より小さい場合：low を +1 します。
     • 合計が sum より大きい場合：high を -1 します。
5. 最後に res を返します。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

def sum_pair(matrix, target):
    res = []
    n = len(matrix)

    # 各行を昇順にソート
    for i in range(n):
        matrix[i].sort()

    # すべての行のペアを確認
    for i in range(n - 1):
        for j in range(i + 1, n):
            low = 0
            high = n - 1
            # ツーポインター法で合計が一致するペアを探索
            while low < n and high >= 0:
                current = matrix[i][low] + matrix[j][high]
                if current == target:
                    res.append((matrix[i][low], matrix[j][high]))
                    low += 1
                    high -= 1
                elif current < target:
                    low += 1
                else:
                    high -= 1
    return res


target = 13
matrix = [
    [2, 4, 3, 5],
    [6, 9, 8, 7],
    [10, 11, 14, 12],
    [13, 1, 15, 16]
]

print(sum_pair(matrix, target))

入力

[[2, 4, 3, 5],
[6, 9, 8, 7],
[10, 11, 14, 12],
[13, 1, 15, 16]]
sum = 13

出力

[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]

計算量について

各行のソートには O(n log n) かかり、行のペアは最大 n×(n-1)/2 通り存在します。さらに各ペアに対してツーポインター走査が O(n) で行われるため、全体の時間計算量は O(n³) となります。行列のサイズが大きい場合は、ハッシュセットを活用した方法なども合わせて検討するとよいでしょう。