Pythonで文字列の文字から作れるすべての組み合わせのリストを求めるプログラム

文字列 s が与えられたとき、その文字を使って作れる「すべての組み合わせ」を求めます。同じ文字の集合からなる文字列が複数存在する場合は、辞書順で最小のものだけを出力します。なお、s に含まれる文字はすべて一意（重複なし）であるという制約があります。

たとえば、入力が s = "pqr" の場合、出力は ['r', 'qr', 'q', 'pr', 'pqr', 'pq', 'p'] のようになります。

解き方の手順

この問題は、文字列を末尾から先頭へ向かって走査し、それまでに生成した部分文字列のそれぞれに現在の文字を連結していくことで解決できます。具体的には次のステップに従います。

• st_arr := 結果を格納する新しい空のリストを作成する
• i を (s の長さ − 1) から 0 まで、1 ずつ減らしながら繰り返す
  • j を 0 から (st_arr の長さ − 1) まで繰り返す
    • (s[i] + st_arr[j]) を st_arr の末尾に追加する
  • s[i] 単体を st_arr の末尾に追加する
• st_arr を返す

実装例

理解を深めるため、以下のPythonコードを確認してみましょう。

def solve(s):
   st_arr = []

   for i in range(len(s)-1,-1,-1):
      for j in range(len(st_arr)):
         st_arr.append(s[i]+st_arr[j])
      st_arr.append(s[i])
   return st_arr

s = "pqr"
print(solve(s))

入力

"pqr"

出力

['r', 'qr', 'q', 'pr', 'pqr', 'pq', 'p']

アルゴリズムのポイント

文字列を右側（末尾）から処理することで、既存の組み合わせすべてに新しい文字を先頭に付け加えたパターンと、その文字単体のパターンが自然に生成されます。これにより、元の文字列での文字の並び順を保ったまま、空集合を除くすべての部分集合が漏れなく列挙されます。

文字が n 個ある場合、非空の部分集合は 2^n − 1 個存在するため、計算量は O(2^n) となります。文字数が増えると組み合わせの総数が爆発的に増加するため、長い文字列を扱う際は注意が必要です。