Pythonで積が等しくなるタプル(a×b=c×d)の個数を求めるプログラム

問題の概要

正の整数が重複なく格納された配列 nums が与えられます。このとき、a × b = c × d を満たすタプル (a, b, c, d) の総数を求めます。ただし、a、b、c、d はすべて nums の要素であり、4つの値は互いに異なる必要があります。

たとえば入力が nums = [2, 3, 4, 6] の場合、出力は 8 になります。条件を満たすタプルは次の 8 通りです。

(2, 6, 3, 4)、(2, 6, 4, 3)、(6, 2, 3, 4)、(6, 2, 4, 3)、(3, 4, 2, 6)、(4, 3, 2, 6)、(3, 4, 6, 2)、(4, 3, 6, 2)

解法のアプローチ

この問題は、「同じ積を持つペアがいくつ存在するか」を辞書で集計し、そこから組み合わせの数を計算することで効率よく解けます。手順は以下のとおりです。

• デフォルト値が 0 の空の辞書(マップ)dic を用意する
• 答えを格納する変数 ans を 0 で初期化する
• i を 0 から(要素数 − 2)まで繰り返す
  • j を i + 1 から(要素数 − 1)まで繰り返し、積 nums[i] * nums[j] の出現回数を dic に記録する
• dic の各値 v に対して次を処理する
  • v が 1 の場合はスキップする(同じ積を持つペアが他に存在しないため)
  • v から 1 を引く
  • s := (v ÷ 2) × (8 + 8 × v) を計算する
  • ans に s を加算する
• ans を整数として返す

計算式のポイント

同じ積 P を持つペアが k 個あるとき、その中から 2 つのペアを選ぶ方法は C(k, 2) = k × (k − 1) ÷ 2 通りです。さらに、選ばれた 2 つのペア (a, b) と (c, d) の並べ方は 8 通りあるため、合計は「C(k, 2) × 8」となります。コード内の式 (v ÷ 2) × (8 + 8 × v)(v = k − 1)は、この値と一致します。

Pythonでの実装例

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

from collections import defaultdict

def solve(nums):
    dic = defaultdict(int)
    ans = 0
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            dic[nums[i]*nums[j]] += 1
    for v in dic.values():
        if v == 1:
            continue
        v = v - 1
        s = (v/2) * (8 + 8*v)
        ans += s
    return int(ans)

nums = [3, 4, 6, 2]
print(solve(nums))

入力

[3, 4, 6, 2]

出力

8

[3, 4, 6, 2] は [2, 3, 4, 6] と同じ要素の並べ替えであるため、先ほどの例と同じく 8 という結果が得られます。

計算量

すべてのペア (i, j) を一度ずつ調べるため、時間計算量は O(n²) です。また、積の出現回数を記録するため、空間計算量も最大で O(n²) となります。4重ループで全探索する O(n⁴) の素朴な方法に比べて、大幅な高速化が可能です。