Pythonでバイナリ行列の重複行を検出！Counterを使った効率的な実装方法

0と1だけで構成されるバイナリ行列が与えられたとき、その中から重複する行を見つけて出力するのが本記事の目的です。Pythonでは標準ライブラリの collections.Counter() を活用することで、この問題を簡潔かつ効率的に解決できます。

実行例

入力：
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0

出力：
(1, 1, 1, 1)
(0, 0, 0, 0)

アルゴリズムの手順

1. 0と1のみで構成されたバイナリ行列を作成します。
2. 辞書には「行」をキー、「その出現頻度」を値として格納します。リストは変更可能（ミュータブル）なため、まず各行をタプルに変換しておきます。
3. Counterメソッドを使って辞書を作成します。
4. 作成した辞書全体を走査します。
5. 出現回数が1より多い行をすべて出力します。

サンプルコード

# バイナリ行列の重複行を見つける関数
from collections import Counter

def binarymatrix(A):
    A = map(tuple, A)          # 各行（リスト）をタプルに変換
    dic = Counter(A)           # 行ごとの出現回数をカウント
    print("Duplicate rows of Binary Matrix ::>")
    for (i, j) in dic.items():
        if j > 1:
            print(i)

# ドライバープログラム
if __name__ == "__main__":
    A = []
    n = int(input("Enter n for n x n matrix : "))   # ここでは 3 を想定
    # 2次元配列はリストとして格納する
    print("Enter the element ::>")
    for i in range(n):
        row = []                       # 行を一時的に保持するリスト
        for j in range(n):
            row.append(int(input()))   # 入力値を行リストに追加
        A.append(row)                  # 完成した行を行列Aに追加
    print(A)
    # 例：[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

    # 2次元配列を行列形式で表示
    print("Display Array In Matrix Form")
    for i in range(n):
        for j in range(n):
            print(A[i][j], end=" ")
        print()
    binarymatrix(A)

実行結果

Enter n for n x n matrix : 4
Enter the element ::>
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
[[1, 1, 1, 1], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]]
Display Array In Matrix Form
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0
Duplicate rows of Binary Matrix ::>
(1, 1, 1, 1)
(0, 0, 0, 0)

ポイント解説

なぜタプルへの変換が必要なのか？

Pythonの辞書やCounterは、キーとして「ハッシュ可能（イミュータブル）」なオブジェクトしか受け付けません。リストは後から内容を変更できるためハッシュ化できず、そのままではキーに使用できません。そこで各行を tuple() でタプルに変換してからCounterに渡しています。

Counterの役割

Counter は要素の出現回数を自動的に集計してくれるクラスです。各行（タプル）を渡すだけで、どの行が何回登場したかを辞書形式で簡単に取得できます。あとは出現回数が2以上の項目だけを取り出せば、重複行の検出は完了です。

この手法の計算量はおよそ O(n×m)（nは行数、mは列数）です。すべての行同士を総当たりで比較する方法（O(n²×m)）に比べて大幅に高速であり、規模の大きい行列を扱う場合にも有効なアプローチといえます。