【Python】停車駅の組み合わせ問題を解くプログラム

本記事では、次の問題に対するPythonでの解き方を詳しく解説します。

問題設定

問題文： 地点Aと地点Bの間に13の中間駅があるものとします。このとき、列車が2つの中間駅に停車する方法のうち、選んだ2駅が隣接しない（連続しない）ような組み合わせが何通りあるかを求めます。

解法のポイント

n個の中間駅から、互いに隣接しないp個の駅を選ぶ方法の総数は、組合せの公式を使って次のように表せます。

C(n − p + 1, p)

今回の場合は n = 13、p = 2 なので、C(12, 2) = 66 通りという答えになります。

実装例

# 停車駅の組み合わせを求める関数
def stopping_station(p, n):
    num = 1
    dem = 1
    s = p
    # 分母：p の階乗を計算
    while p != 1:
        dem *= p
        p -= 1
    # 分子：(n - s + 1) から順に積を計算
    t = n - s + 1
    while t != (n - 2 * s + 1):
        num *= t
        t -= 1
    if (n - s + 1) >= s:
        return int(num / dem)
    else:
        # 条件を満たす選び方が存在しない場合
        return -1

# メイン処理
num = stopping_station(2, 13)
if num != -1:
    print("停車駅の組み合わせ数:", num)
else:
    print("条件を満たす組み合わせは存在しません")

出力結果

停車駅の組み合わせ数: 66

コードの解説

使用している変数はすべてローカルスコープで宣言されており、それぞれの役割は以下のとおりです。

• s / p： 停車させる駅の数（今回は2）
• n： 中間駅の総数（今回は13）
• dem： 組合せ計算の分母（p の階乗）
• num： 組合せ計算の分子
• 戻り値 -1： 条件を満たす組み合わせが存在しないことを示す値

「(n − s + 1) >= s」という条件判定により、非連続でp駅を選ぶことが物理的に可能かどうかをチェックしています。駅の数が足りず選び方が存在しない場合は -1 を返し、呼び出し元でその旨を表示します。

まとめ

本記事では、Pythonを使って「停車駅の組み合わせ」問題を解く方法を学びました。組合せの公式 C(n − p + 1, p) を活用することで、隣接しない駅の選び方を効率的に求められます。この考え方は、間隔を空けて対象を選ぶ問題全般に応用できるため、座席配置やスケジューリングなどの課題にも役立ちます。