Pythonでリストの要素が等差数列（AP）を形成しているか判定するプログラム

はじめに

数値のリスト nums が与えられたとき、その要素が等差数列（Arithmetic Progression：AP）を形成しているかどうかを判定するプログラムを作成します。等差数列とは、隣り合う任意の2つの要素の差（公差）が常に一定である数列のことです。

例えば、入力が nums = [9,1,17,5,13] の場合、要素を昇順にソートすると [1,5,9,13,17] となり、隣接する要素同士の差はすべて4で一定です。したがって、この場合の出力は True になります。

解決の手順

この問題は、以下の手順で解くことができます。

• リスト nums を昇順にソートします。
• nums の要素数が1より大きい場合は、公差 const を「nums[1] - nums[0]」として求めます。
• 要素数が1以下の場合は、公差を比較する必要がないため True を返します。
• インデックス0から「要素数 - 1」までループ処理を行い、各隣接要素の差 nums[i+1] - nums[i] が const と一致しない場合は False を返します。
• ループが最後まで完了すれば、すべての差が一致しているため True を返します。

Pythonでの実装例

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

def solve(nums):
    nums = sorted(nums)

    if len(nums) > 1:
        const = nums[1] - nums[0]
    else:
        return True
    for i in range(len(nums)-1):
        if nums[i+1] - nums[i] != const:
            return False
    return True

nums = [9,1,17,5,13]
print(solve(nums))

入力

[9,1,17,5,13]

出力

True

補足：計算量について

このアルゴリズムでは、ソートに O(n log n)、隣接要素の比較に O(n) の時間計算量が必要となります。全体としての計算量は O(n log n) であり、要素数が多いリストでも効率的に判定できます。

なお、ソートせずに「最大値・最小値・要素数」から公差を推定し、集合を使って各要素の存在を確認する方法（O(n)）もありますが、重複要素の扱いなど注意点があるため、シンプルさと正確性を重視するなら本記事のソートベースの手法がおすすめです。