アナグラムの生成【Python】

Pythonを使って、アナグラムを生成するプログラムを作ってみます。

アナグラムとは

アナグラムとは、ある文字列中に存在する文字を入れ替えて別の言葉を作る一種の言葉遊びのようなものです。

例えば、自由の女神はStatue of Libertyですが、この中に存在する文字を入れ替えると、Built To Stay Freeになります。

他にも、学生寮 dormitoryのアナグラムは dirty roomになります。

このようなアナグラムを生成するプログラムを書いていきます。

Itertoolを使用した場合

パーミュテーションを使用して、総当たりでアナグラムを探索してみます。

二分探索

膨大な単語の中に、アナグラム生成前の文字列の断片が存在するかどうかを確認する際に、単語リストの全域を探索すると膨大な時間がかかるので、二分探索を行う関数を作っておきます。

def bs(target:str,words:list[str]) -> bool:
    l:int = len(words)
    left:int = 0
    right:int = l-1
    mid:int = (left+right)//2
    i:int = 0
    if words[left] == target or words[right] == target:
        return True
    while i<=math.log2(l):
        if words[mid] == target:
            return True
        elif words[mid] > target:
            right = mid 
            mid = (left+right)//2
        else:
            left = mid
            mid = (left+right)//2
        i += 1
    return False

探索の際にこの関数を使用することで、30万回の探索回数を19回までに落とすことができます。

アナグラムの検証関数

探索結果のうち、アナグラムの定義に当てはまらないものを弾く関数を作成します。

def is_valid(word:str,target:str) -> bool:
    for i in word:
        if word.count(i) != target.count(i):
            return False
    return True

アナグラム探索関数

def get_anagrams(letter_pool) -> set[str]:
    word_length:int = len(letter_pool)
    l:list[str] = [i for i in letter_pool]
    with open('dict.txt') as fp:
        words = [i.replace("\n","") for i in fp.readlines()]
    candidates = ["".join(c)  for n in range(1,len(l)+1)  for c in itertools.permutations(l,n)]
    valid_candidates = [i for i in candidates if bs(i,words)]
    all_patterns = [list(i) for i in itertools.combinations(valid_candidates,2) if len(i[0]+i[1]) == word_length]
    result =  [i for i in all_patterns if is_valid("".join(i),letter_pool)]
    result = result+ [i[::-1] for i in result]
    return {" ".join(i) for i in result}

一旦これでアナグラムを探索することはできるようになりましたが、計算量が$O(n!)$になっているので、現実的ではありません。

例えば、文字数16の文字についてアナグラムを探索しようとすると、20922789888000パターンのパーミュテーションを生成することになり、現実的ではありません。

そのため、$O(n!)\to O(n^2)$となるようなアルゴリズムについて考えます。

イテレーションのみ

考え方自体はitertoolの時と似ていますが、無駄な組み合わせを生成する前に、アナグラムの条件に該当しないものをカットするため、大幅な時間削減ができるかと思います。

def isIn(word:str,l:list[str]) -> bool:
    for i in word:
        if i not in l:
            return False
    return True

def isSameLength(word1:str,word2:str,target:str) -> bool:
    if len(word1) + len(word2) == len(target):
        return True
    return False

def isValid(w:str,l:list[str]) -> bool:
    for i in w:
        if w.count(i) != l.count(i):
            return False
    return True

def get_anagrams(letter_pool) -> set[str]:
    with open("dict.txt","r") as fp:
        words = [i.replace("\n","") for i in fp.readlines()]
    letter_pool_list:list[str] = [i for i in letter_pool]
    candidates:list[str] = [i for i in words if isIn(i,letter_pool_list)]
    result:list[str] = []
    for i in range(len(candidates)):
        for j in range(len(candidates)):
            if i != j:
                if isSameLength(candidates[i],candidates[j],letter_pool) and isValid(candidates[i]+candidates[j],letter_pool):
                    result.append(candidates[i]+" "+candidates[j])
    return set(result)