Pythonで文字の繰り返しを含むすべての順列（組み合わせ）を生成する方法

特定の文字セットから、同じ文字を何度でも使えるようにしてすべての組み合わせ（重複ありの順列）を取得したいケースはよくあります。この記事では、インデックス値を活用して繰り返しの組み合わせを生成し、結果を出力するメソッドを定義する方法を解説します。

サンプルコード

以下に実装例を示します。

def to_string(my_list):
   return ''.join(my_list)

def lex_recurrence(my_string, my_data, last_val, index_val):
   length = len(my_string)

   for i in range(length):

      my_data[index_val] = my_string[i]

      if index_val==last_val:
         print(to_string(my_data))
      else:
         lex_recurrence(my_string, my_data, last_val, index_val+1)

def all_lex(my_string):
   length = len(my_string)

   my_data = [""] * (length+1)
   my_string = sorted(my_string)
   lex_recurrence(my_string, my_data, length-1, 0)

my_string = "MQ"
print("The string is :")
print(my_string)
print("All permutations with repetition of " + my_string + " are...")
all_lex(my_string)

出力結果

The string is :
MQ
All permutations with repetition of MQ are...
MM
MQ
QM
QQ

コードの解説

• まず「to_string」というメソッドを定義します。リストを引数として受け取り、すべての要素を連結した1つの文字列を返します。

• 次に「lex_recurrence」というメソッドを定義します。このメソッドは文字列とインデックス値を引数として受け取り、組み合わせの生成を担当します。

• 文字列の長さ分だけループ処理を行い、現在の位置に各文字を順番に設定していきます。

• そのうえで、最後の値（last_val）と現在のインデックス値が一致しているかどうかを判定します。

• 一致している場合は、その時点で1つの組み合わせが完成しているため、結果として出力します。

• 一致していない場合は、インデックス値を1つ増やして自分自身を再帰的に呼び出します。これにより、すべての組み合わせが網羅的に生成されます。

• さらに「all_lex」というメソッドを定義します。「sorted」関数で文字列を事前にソートしてから、先ほどの再帰メソッドを呼び出します。ソートしておくことで、結果が辞書順に整然と出力されるのがポイントです。

• メソッドの外側では、対象となる文字列を定義してコンソールに表示し、続いて生成されたすべての組み合わせが出力されます。

補足：itertoolsを使ったより簡潔な方法

Pythonの標準ライブラリ「itertools」を利用すれば、同様の処理をより短く書くこともできます。

from itertools import product

my_string = "MQ"
for combo in product(my_string, repeat=len(my_string)):
    print(''.join(combo))

product関数のrepeat引数に文字列の長さを指定するだけで、重複を許すすべての順列を簡単に生成できます。実務ではこちらの方がシンプルで読みやすいコードになるためおすすめです。