Pythonプログラム：（基数、数値）ペアの配列内で一致する組み合わせの数を見つける方法

(x, y) 形式の複数のペアが与えられます。ここで、x は数値の基数（base）を、y はその数値そのものを表します。リストの中には、異なる表記でありながら同じ値を意味するペアが存在する場合があります。そこで、与えられた数値ペアの中に一致する組み合わせがいくつあるかを調べる必要があります。なお、入力には重複したペアや、無効な基数と数値の組み合わせが含まれる可能性もあります。

例として、num_inputs = 2、input_arr = [(10, 15), (8, 17)] の場合の出力は 1 になります。

変数 num_inputs は入力の個数を示し、配列 input_arr は数値ペアの一覧を表します。この2つのペアを見てみると、10進法における 15 は、8進法（オクタル）における 17 とまったく同じ値です。つまり一致は1件だけなので、出力として 1 を返します。

解決のための手順

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

• arr_len := input_arr のサイズ
• temp_dict := 整数値を格納する新しいマップ（辞書）
• i を 0 から num_inputs まで繰り返します。
  • num_base := input_arr の i 番目のペアの最初の数値を文字列化したもの
  • num_val := input_arr の i 番目のペアの2番目の数値を文字列化したもの
  • temp_dict[int(num_val, int(num_base))] := temp_dict[int(num_val, int(num_base))] + 1
• cnt := 0
• temp_dict のすべての値について、cnt := cnt + value × ((value − 1) / 2) の切り捨て値を加算します。
• cnt を返します。

アルゴリズムのポイント

Python の組み込み関数 int() は、第2引数に基数を指定することで、任意の進法の文字列を10進数の整数に変換できます。これにより、「15（10進法）」と「17（8進法）」のような異なる表記を共通の整数値に正規化し、辞書を使って同じ値を持つペアをグループ化できます。

最終的なカウントでは、同じ値に属する n 個のペアから選べる組み合わせの総数 nC2 = n × (n − 1) / 2 を計算しています。これにより、互いに一致するペアの組をすべて数え上げることができます。

実装例

理解を深めるために、以下の実装例をご覧ください。

from collections import defaultdict
def solve(num_inputs, input_arr):
    arr_len = len(input_arr)
    temp_dict = defaultdict(int)
    for i in range(num_inputs):
        num_base, num_val = str(input_arr[i][0]), str(input_arr[i][1])
        temp_dict[int(num_val, int(num_base))] += 1
    cnt = 0
    for value in temp_dict.values():
        cnt += value*(value - 1)//2
    return cnt
print(solve(2, [(10, 15), (8, 17)]))

入力

2, [(10, 15), (8, 17)]

出力

1