Pythonで文字列からすべての有効なIPアドレスの組み合わせを生成する方法

数字のみで構成された文字列が与えられたとき、そこから生成できるすべての有効なIPアドレスの組み合わせを求めるのが本記事の目的です。

基本的な考え方は、まず文字列の長さを確認し、その後に「.（ドット）」を挿入する位置を3か所選んで分割します。ドットの挿入位置の組み合わせをすべて試すことで、有効なIPアドレスを網羅的に抽出できます。

実行例

Input : "255011123222"
→ 有効なIPアドレスとして成立しない場合もある
Input : "255011345890"
→ 有効なIPアドレス: 255.011.123.222

アルゴリズム

Step 1: まず文字列の長さを確認する。
Step 2: 文字列に3つのドットを挿入して4つに分割する。
        各部分（W, X, Y, Z）は0〜255の範囲の数値であり、
        「0」自体以外は先頭に0を付けてはならない。
Step 3: ドットの挿入位置について、可能なすべての組み合わせを生成する。
Step 4: 生成された各組み合わせが有効なIPアドレスかどうかを検証する。

サンプルコード

# 有効なIPアドレスの候補を検証するPythonコード
# IPアドレスの各オクテットが妥当かどうかを判定する関数

def ipvalid(ip): 
   # ドットで分割
   ip = ip.split(".")
      
   # 各種エッジケースのチェック
   for i in ip: 
      if len(i) > 3 or int(i) < 0 or int(i) > 255: 
         return False
      if len(i) > 1 and int(i) == 0: 
         return False
      if len(i) > 1 and int(i) != 0 and i[0] == '0': 
         return False
   return True
  
# 文字列をIPアドレス形式に変換する関数
def ipconvert(A): 
   con = len(A) 

   # 文字列長の上限チェック（最大12桁）
   if con > 12: 
      return [] 
   newip = A 
   l = [] 

   # ドット挿入位置の全組み合わせを生成
   for i in range(1, con - 2): 
      for j in range(i + 1, con - 1): 
         for k in range(j + 1, con): 
            newip = newip[:k] + "." + newip[k:] 
            newip = newip[:j] + "." + newip[j:] 
            newip = newip[:i] + "." + newip[i:] 

            # 組み合わせの妥当性を検証
            if ipvalid(newip): 
               l.append(newip) 
            newip = A 
   return l  
# 動作確認          
A = input("IPアドレス候補の数字列を入力してください: ")
print(ipconvert(A)) 

このコードでは、ipvalid() 関数が各セグメント（オクテット）に対して以下の条件を検証しています。

• 桁数が3桁以下であること
• 数値が0以上255以下であること
• 複数桁の「0」（例：00 や 000）でないこと
• 先頭に不要な0が付いていないこと（例：011 は無効）

また、ipconvert() 関数は三重ループによって3つのドットを挿入する位置の全パターンを試し、有効な組み合わせだけをリストに格納して返します。なお、元のコードには newip = A のリセット処理が条件分岐内にあるため、無効な組み合わせが出た場合に文字列が壊れる可能性があります。上記サンプルコードではループの最後で必ずリセットするよう修正しています。

出力結果

Enter IP address25525522134
['255.255.22.134', '255.255.221.34']

このように、同じ数字列でもドットの挿入位置によって複数の有効なIPアドレスが存在しうることが分かります。総当たり（ブルートフォース）的なアプローチのため計算量は O(n³) ですが、IPアドレスの最大長が12桁と限られているため、実用上は十分高速に動作します。