Pythonで数値リストを同じ要素のグループに分割できるか判定する方法

数値のリスト nums が与えられたとき、そのリストを1つ以上のグループに分割できるかどうかを判定する問題を考えます。分割は以下の3つの条件をすべて満たす必要があります。

1. 各グループのサイズが2以上であること
2. すべてのグループのサイズが同じであること
3. 各グループ内のすべての数値が同じであること

例えば、入力が [3, 4, 6, 9, 4, 3, 6, 9] の場合、出力は True になります。このリストは [3, 3]、[4, 4]、[6, 6]、[9, 9] という4つのグループに分割でき、各グループのサイズは2で揃っており、グループ内の要素もすべて同じだからです。

解法のアプローチ

この問題の鍵となるのは「各要素の出現回数」です。すべての要素の出現回数の最大公約数(GCD)が2以上であれば、そのGCDをグループのサイズとして、すべての要素を条件を満たすグループに均等に分割できます。逆に、GCDが1であればどのような分割方法でも条件を満たせません。

具体的な手順は以下の通りです。

• counts: 各要素をキー、出現回数を値とするマップ(Counter)を作成する
• temp: 0で初期化する
• counts 内の各出現回数について以下を繰り返す
  • temp が 0 の場合、その出現回数を temp に代入する
  • それ以外の場合、temp とその出現回数の最大公約数を計算して temp に代入する
  • temp が 1 になった時点で False を返す
• ループが最後まで完了すれば True を返す

実装例

from collections import Counter
import math
class Solution:
    def solve(self, nums):
        counts = Counter(nums)
        temp = 0
        for count in counts:
            if temp == 0:
                temp = counts[count]
            else:
                temp = math.gcd(counts[count], temp)
                if temp == 1:
                    return False
        return True
ob = Solution()
L = [3, 4, 6, 9, 4, 3, 6, 9]
print(ob.solve(L))

入力

[3, 4, 6, 9, 4, 3, 6, 9]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n + k log m) です(n はリストの長さ、k はユニークな要素の数、m は最大の出現回数)。リストを一度走査してカウントし、その後ユニークな要素ごとにGCD計算を行うだけなので、非常に効率的な解法と言えます。