Python
 Computer >> コンピューター >  >> プログラミング >> Python

アナグラム単語の最大サブセットのサイズを見つけるPythonプログラム


小文字の配列が与えられます。私たちのタスクは、互いのアナグラムである文字列の最大のサブセットのサイズを見つけることです。文字列のアナグラムは、2番目の文字列が最初の文字列の単なる再配置である場合、1つの文字列が別の文字列のアナグラムであることを意味します。ここでは、Counter()メソッドを使用してPythonでこの問題をすばやく解決できます。

たとえば、文字列「python」と「typhon」はアナグラムです。

アルゴリズム

Step 1: Split input string separated by space into words.
Step 2: sort each string in given list of strings
Step 3: now create a dictionary using a counter method which will have strings as key and their Frequencies as value.
Step 4: get maximum value of frequency using max function.

サンプルコード

# Function to find the size of largest subset 
# of anagram words from collections import Counter
def largestana(str1):
   # split input string separated by space
   str1 = str1.split(" ")
   # sort each string in given list of strings
   for i in range(0,len(str1)):
      str1[i]=''.join(sorted(str1[i]))
   # now create a dictionary using the counter method
   # which will have strings as key and their
   # frequencies as the value
   newstr1 = Counter(str1)
   # get maximum value of frequency
   print ("The Size Of largest subset of Anangram word is ::>",max(newstr1.values()))
   # Driver program
   if __name__ == "__main__":
      str1 = input("Enter the string ::>")
      largestana(str1)

出力

Enter the string ::>qwe ewq rty ytr ytr ytr
The Size Of largest subset of Anangram word is ::> 4

  1. グラフ内の最大のクリークの最小サイズを見つけるプログラム(Python)

    グラフが与えられ、グラフ内の最大のクリークの最小サイズを見つけるように求められたとします。グラフのクリークは、頂点のすべてのペアが隣接している、つまり頂点のすべてのペアの間にエッジが存在するグラフのサブセットです。グラフ内で最大のクリークを見つけることは多項式時間では不可能であるため、小さなグラフのノードとエッジの数を考えると、グラフ内の最大のクリークを見つける必要があります。 したがって、入力がノード=4、エッジ=4のような場合。その場合、出力は2になります。 上のグラフでは、クリークの最大サイズは2です。 これを解決するには、次の手順に従います- 関数helper()を定義し

  2. 配列内の最大の要素を見つけるPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −配列が与えられたので、配列の最大要素を計算する必要があります。 ここでは、ループ全体をトラバースして最大の要素を計算し、要素を取得するブルートフォースアプローチを使用します。 以下の実装を観察できます。 例 # largest function def largest(arr,n):    #maximum element    max = arr[0]    # traverse the whole loop    for