Pythonで等価なドミノペアの数を効率的に数える方法

ドミノのリストが与えられているとします。各ドミノは2つの数字を持っています。2つのドミノ D[i] = [a, b] と D[j] = [c, d] は、「a = c かつ b = d」または「a = d かつ b = c」が成り立つ場合に等しいとみなされます。つまり、ドミノは反転しても同一視できるということです。

ここでの課題は、0 <= i < j < ドミノの総数 を満たし、D[i] が D[j] と等価であるようなペア (i, j) の個数を求めることです。

例えば、ドミノのリストが [[1, 2], [2, 1], [3, 4], [6, 5]] の場合、[1, 2] と [2, 1] が反転関係にあるため、出力は 1 になります。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• answer = 0 として初期化する
• ドミノリスト内の各ペア p に対して:
  • ペア p をソートして正規化する([2, 1] → [1, 2])
  • 各正規化済みドミノの出現頻度を辞書 D に記録する
• 辞書 D の各値 b に対して:
  • answer := answer + (b × (b − 1)) ÷ 2 を加算する
• answer を返す

なぜ b × (b − 1) ÷ 2 なのか?

同じキー(ソート済みペア)を持つドミノが b 個存在する場合、その中から2つを選ぶ組み合わせの総数は二項係数 C(b, 2) = b × (b − 1) ÷ 2 で表されます。この公式を使うことで、すべての等価ペアを効率的に数え上げることができます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution(object):
    def numEquivDominoPairs(self, dominoes):
        d = {}
        ans = 0
        for i in dominoes:
            i.sort()
            i = tuple(i)
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        for b in d.values():
            ans += ((b * (b - 1)) // 2)
        return ans

ob1 = Solution()
print(ob1.numEquivDominoPairs([[1,2],[2,1],[3,4],[5,6],[4,3]]))

入力

[[1,2],[2,1],[3,4],[5,6],[4,3]]

出力

2

この例では、[1, 2] と [2, 1]、そして [3, 4] と [4, 3] の2組が等価なペアとなるため、結果は 2 になります。

計算量の分析

このアルゴリズムの時間計算量は O(n log n)(n 個のペアそれぞれをソートするため)、空間計算量は O(n) です。すべてのペアを総当たりで比較する O(n²) の素朴なアプローチと比較して、大幅に効率的である点が大きなメリットです。