Pythonでドメイン(定義域)と範囲(値域)が関数を形成しているか判定するプログラム

問題の概要

ドメイン(定義域)を表すリスト x と、範囲(値域)を表すリスト y が与えられます。両者のサイズは同じで、すべての要素は正の整数とします。このとき、対応関係「x → y」が数学的な意味で関数になっているかどうかを判定するプログラムを作成しましょう。

関数であるためには、定義域の各要素に対して、値域の要素がただ一つ対応していなければなりません。つまり、同じ x の値に異なる y の値が対応しているようなデータの場合、それは関数とは言えません。

入力例と出力例

たとえば、次のような入力を考えてみます。

• x = [1, 3, 2, 6, 5]
• y = [1, 9, 4, 36, 25]

この場合の出力は True になります。各 x に対応する y がそれぞれその2乗の値(1→1、3→9、2→4、6→36、5→25)になっており、すべての x が一意の y に対応しているためです。

一方、同じ x の値に対して異なる y が割り当てられているペアがひとつでも含まれていれば、結果は False となります。

解法のアプローチ

この問題は、辞書(マップ)を使うことでシンプルに解けます。手順は以下の通りです。

1. 空の辞書 mp を用意します。
2. i を 0 から x のサイズまで順に処理します。
   • a := x[i]、b := y[i] とします。
   • a がまだ mp に存在しない場合は、mp[a] := b として登録します。
   • a がすでに mp に存在する場合は、同じ定義域の要素に複数の対応が発生していることになるため、False を返します。
3. ループが最後まで完了すれば、すべての対応が一意であることが分かるので、True を返します。

ここでは分かりやすいシンプルな手順で説明していますが、より複雑な実装にすることも可能です。ポイントは、辞書のキー重複チェックによって対応の一意性を検証できるという点にあります。

Pythonでの実装例

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

def solve(x, y):
    mp = {}
    for i in range(len(x)):
        a = x[i]
        b = y[i]
        if a not in mp:
            mp[a] = b
        else:
            return False
    return True

x = [1,3,2,6,5]
y = [1,9,4,36,25]
print(solve(x, y))

入力

[1,3,2,6,5], [1,9,4,36,25]

出力

True

計算量と補足

このアルゴリズムは、リストを一度だけ走査するため時間計算量は O(n)、辞書に最大 n 個のキーを格納するため空間計算量も O(n) となります。

なお、厳密に言えば、同じ (x, y) のペアが重複して現れるケースは依然として関数とみなせます。上記のシンプルな実装ではキーの重複があれば一律 False を返すため、そのようなケースまで厳密に扱いたい場合は、「a が既に mp に存在し、かつ mp[a] != b のときのみ False を返す」ように条件を変更するとよいでしょう。

また、zip を使うとインデックス操作なしでより簡潔に書くこともできます。

def solve(x, y):
    mp = {}
    for a, b in zip(x, y):
        if a in mp:
            return False
        mp[a] = b
    return True