Pythonで数値の各桁に対応する文字から生成できるすべての文字列を求める方法

ここでは、1から9までの各数字が複数の文字に対応付けられた「文字マッピング」を扱います。次のようなマッピングを考えてみましょう。

1 -> ['A', 'B', 'C']
2 -> ['D', 'E', 'F']
3 -> ['G', 'H', 'I']
4 -> ['J', 'K', 'L']
5 -> ['M', 'N', 'O']
6 -> ['P', 'Q', 'R']
7 -> ['S', 'T', 'U']
8 -> ['V', 'W', 'X']
9 -> ['Y', 'Z']

問題の概要

ある数値が与えられたとき、その各桁をマッピング表内の対応する文字に置き換えて、生成されるすべての文字列を表示します。ただし、重要なルールとして同じ数字が数値の中で複数回現れる場合は、必ず毎回同じ文字を使用する必要があります。また、入力される数値には0は含まれないものとします。

たとえば入力が [4, 3, 5] の場合、出力は次のようになります。

JGM KGM LGM JHM KHM LHM JIM KIM LIM JGN KGN LGN JHN KHN LHN JIN KIN LIN JGO KGO LGO JHO KHO LHO JIO KIO LIO

解法のアプローチ

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

• out:結果を格納する新しいリスト
• temp:一時的な結果を保持する新しいリスト
• char_map:各数字が最初に出現した位置(インデックス)を記録する辞書
• index:現在処理中の桁の位置(初期値は0)

続いて、入力の各桁に対して次の処理を行います。

1. その数字が char_map に登録されていなければ、char_map[digit] = index として初出位置を記録します。
2. temp リストをクリアします。
3. 対応する文字リスト table[digit - 1] の各文字について処理を繰り返します。
   • 最初の桁(index == 0)の場合: 各文字をそのまま out に追加します。
   • 2桁目以降(index > 0)の場合: out 内の既存の各文字列に対して、候補の文字を末尾に連結したものを temp に追加します。ただし、その数字がすでに出現済み(char_map[digit] != index)の場合は、新しい文字を連結する代わりに初出時に使った位置の文字をそのまま再利用し、それ以上の組み合わせ展開は行わずにループを抜けます。
4. 2桁目以降であれば、out を temp のコピーで更新します。
5. index を1増やして次の桁へ進みます。

すべての桁を処理し終えたら、out を返します。この仕組みにより、同じ数字が再登場しても文字の選択肢が増殖せず、「同じ数字には常に同じ文字」という制約が自然に満たされます。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def findCombinations(inp, table):
    out = list()
    temp = list()
    char_map = dict()
    index = 0
    for digit in inp:
        if digit not in char_map:
            char_map[digit] = index
        temp.clear()
        for i in range(len(table[digit - 1])):
            if index == 0:
                s = table[digit - 1][i]
                out.append(s)
            if index > 0:
                for string in out:
                    s = table[digit - 1][i]
                    if char_map[digit] != index:
                        s = string[char_map[digit]]
                    string = string + s
                    temp.append(string)
                if char_map[digit] != index:
                    break
        if index > 0:
            out = temp.copy()
        index += 1
    return out

mapping = [['A', 'B', 'C'],
           ['D', 'E', 'F'],
           ['G', 'H', 'I'],
           ['J', 'K', 'L'],
           ['M', 'N', 'O'],
           ['P', 'Q', 'R'],
           ['S', 'T', 'U'],
           ['V', 'W', 'X'],
           ['Y', 'Z']]

inp = [4, 3, 5]
res = findCombinations(inp, mapping)
for it in res:
    print(it, end=" ")

入力

[4, 3, 5]

出力

JGM KGM LGM JHM KHM LHM JIM KIM LIM JGN KGN LGN JHN KHN LHN JIN KIN LIN JGO KGO LGO JHO KHO LHO JIO KIO LIO

計算量について

各桁の文字候補は最大3個なので、n個の異なる数字が含まれる場合、生成される文字列の総数は最大でも 3ⁿ 個になります。一方、すでに出現した数字については文字の選択肢が増えないため、同じ数字の繰り返しが多い入力ほど結果の件数は抑えられます。この性質により、無駄な組み合わせの生成を避けつつ効率的にすべての文字列を列挙できます。