【Python】文字列を構築するのに必要な最小要素数を取得する方法

ある文字列を構築するために必要な最小の要素数を求めるには、set(集合)、combinations(組み合わせ)、issubset(部分集合判定)といった機能と、シンプルな反復処理を組み合わせて使用します。この記事では、具体的なサンプルコードとともに、その仕組みをわかりやすく解説します。

サンプルコード

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

from itertools import combinations

my_list = ["python", "is", "fun", "to", "learn"]

print("The list is :")
print(my_list)

my_target_str = "onis"

my_result = -1
my_set_string = set(my_target_str)
complete_val = False
for value in range(0, len(my_list) + 1):

   for sub in combinations(my_list, value):

      temp_set = set(ele for subl in sub for ele in subl)

      if my_set_string.issubset(temp_set):
         my_result = value
         complete_val = True
         break
   if complete_val:
      break

print("The result is :")
print(my_result)

出力結果

The list is :
['python', 'is', 'fun', 'to', 'learn']
The result is :
2

処理の流れと解説

• まず、itertoolsモジュールからcombinations(組み合わせ生成関数)を環境にインポートします。

• 文字列のリストを定義し、コンソールに表示します。

• 構築の対象となる文字列を別途定義します。

• 対象文字列をset()関数で文字の集合(セット)に変換します。

• 0からリストの要素数までの範囲でループを回しながら、リスト内の要素から取りうるすべての組み合わせをcombinationsで順に取得します。

• 各組み合わせに含まれるすべての文字を集め、一時的なセットに変換します。

• issubsetメソッドを使って、対象文字列のセットがその組み合わせのセットに含まれているかどうかを判定します。

• 条件を満たした場合、変数に「True」を代入して内側のループを抜けます。

• 最終的にこのフラグが「True」であれば、外側のループも終了し、結果がコンソールに表示されます。

このアルゴリズムでは、組み合わせのサイズが小さい順に探索するため、最初に見つかった組み合わせの要素数が自動的に「最小要素数」となります。該当する組み合わせが存在しない場合は、初期値である「-1」が出力される点にも注目してください。