Как найти анаграммы, используя 3 слова в тексте, имеющем список слов?

Question

У меня есть текст и список из 60 тысяч слов. Мне нужно найти анаграммы текста из списка слов, используя 3 слова (длится в алфавитном порядке), и функция должна возвращать кортеж из 3 слов, которые строят анаграмму данного текста. ПРИМЕЧАНИЕ. Я должен игнорировать заглавные буквы и пробелы в тексте.

Я разработал функцию, которая находит все слова из списка слов, которые содержатся в тексте. но я не знаю, как закончить поиск анаграмм.

   def es3(words_list, text):
        text=text.replace(" ","")
        for x in text:
        text=text.replace(x,x.lower())

        result=[]
        cont=0
        for x in words_list:
            if len(x)>=2:
                for c in x:
                    if c in text:
                        cont+=1
                        if cont==len(x):
                            result.append(x)
            cont=0


           Examples:
          text =   "Andrea Sterbini"  -> anagram= ('treni', 'sia', 'brande')
            sorted(andreasterbini)==sorted(treni+sia+brande) 


            "Angelo Monti"          -> ('toni', 'nego', 'mal')
            "Angelo Spognardi"      -> ('sragion', 'pend', 'lago')
            "Ha da veni Baffone"    -> ('video', 'beh', 'affanna')

Answer 1

Наивный алгоритм будет:

• взять каждый триплет слов и добавить элемент (sorted letters of the three words, triplet) в мультикарту (карту, которая может принимать более одного значения на ключ: в Python, карта reglar key -> [values]).
• сортирует буквы искомого текста и выводит связанные значения в мультикарте.

Проблема в том, что построение мультикарты имеет O(N^3) сложность времени и пространства. Если N = 60 000, у вас есть 216 000 миллиардов операций и значений. Это много!

Давайте попробуем уменьшить это. Позвольте мне перефразировать проблему: по заданной последовательности найдите три подпоследовательности, которые: 1. не перекрываются и охватывают эту последовательность; 2. находятся в данном наборе. Смотрите ваш первый пример: "Анджело Монти" -> ('toni', 'nego', 'mal')

sequence    a e g i l m n n o o t
subseq1           i     n   o   t
subseq2       e g         n   o
subseq3     a       l m

Найти три непересекающихся подпоследовательности, которые покрывают последовательность, является той же проблемой, что и разделение набора из n элементов на k групп. Сложность известна как S (n, k) , которая ограничена 1/2 (n k) k^(n-k). Следовательно, поиск всех разбиений n элементов в k группах имеет сложность O(n^k * k^(n-k)).

Давайте попробуем реализовать это в Python:

def partitions(S, k):
    if len(S) < k: # can't partition if there are not enough elements
        raise ValueError()
    elif k == 1:
        yield tuple([S]) # one group: return the set
    elif len(S) == k:
        yield tuple(map(list, S)) # ([e1], ..., [e[n]])
    else:
        e, *M = S # extract the first element
        for p in partitions(M, k-1): # we need k-1 groups because...
            yield ([e], *p) # the first element is a group on itself
        for p in partitions(M, k):
            for i in range(len(p)): # add the first element to every group
                yield tuple(list(p[:i]) + [[e] + p[i]] + list(p[i+1:]))

Простой тест:

>>> list(partitions("abcd", 3))
[(['a'], ['b'], ['c', 'd']), (['a'], ['b', 'c'], ['d']), (['a'], ['c'], ['b', 'd']), (['a', 'b'], ['c'], ['d']), (['b'], ['a', 'c'], ['d']), (['b'], ['c'], ['a', 'd'])]

Теперь я буду использовать в качестве списка слов некоторые слова, которые вы использовали в своем вопросе:

words = "i have a text and a list of words i need to find anagrams of the text from the list of words using words lasts in alphabetic order and the function should return a tuple of the words that build an anagram of the given text note i have to ignore capital letters and spaces that are in the text i have developed the function that finds all the words of the list of words that are contained in the text but i dont know how to end finding the anagrams and some examples treni sia brande toni nego mal sragion pend lago video beh affanna".split(" ")

И построить дикт sorted(letters) -> list of words, чтобы проверить группы

word_by_sorted = {}
for w in words:
    word_by_sorted.setdefault("".join(sorted(w)), set()).add(w)

Результат:

>>> word_by_sorted
{'i': {'i'}, 'aehv': {'have'}, 'a': {'a'}, 'ettx': {'text'}, 'adn': {'and'}, 'ilst': {'list'}, 'fo': {'of'}, 'dorsw': {'words'}, 'deen': {'need'}, 'ot': {'to'}, 'dfin': {'find'}, 'aaagmnrs': {'anagrams'}, 'eht': {'the'}, 'fmor': {'from'}, 'ginsu': {'using'}, 'alsst': {'lasts'}, 'in': {'in'}, 'aabcehilpt': {'alphabetic'}, 'deorr': {'order'}, 'cfinnotu': {'function'}, 'dhlosu': {'should'}, 'enrrtu': {'return'}, 'elptu': {'tuple'}, 'ahtt': {'that'}, 'bdilu': {'build'}, 'an': {'an'}, 'aaagmnr': {'anagram'}, 'eginv': {'given'}, 'enot': {'note'}, 'eginor': {'ignore'}, 'aacilpt': {'capital'}, 'eelrstt': {'letters'}, 'acepss': {'spaces'}, 'aer': {'are'}, 'ddeeelopv': {'developed'}, 'dfins': {'finds'}, 'all': {'all'}, 'acdeinnot': {'contained'}, 'btu': {'but'}, 'dnot': {'dont'}, 'know': {'know'}, 'how': {'how'}, 'den': {'end'}, 'dfgiinn': {'finding'}, 'emos': {'some'}, 'aeelmpsx': {'examples'}, 'einrt': {'treni'}, 'ais': {'sia'}, 'abdenr': {'brande'}, 'inot': {'toni'}, 'egno': {'nego'}, 'alm': {'mal'}, 'aginors': {'sragion'}, 'denp': {'pend'}, 'aglo': {'lago'}, 'deiov': {'video'}, 'beh': {'beh'}, 'aaaffnn': {'affanna'}}

Теперь соберите все кубики вместе: проверьте каждый раздел text на три группы и выведите слова, если эти три группы являются анаграммой слова в списке:

for p in partitions("angelomonti", 3):
    L = [word_by_sorted.get("".join(sorted(xs)), set()) for xs in p]
    for anagrams in itertools.product(*L):
        print (anagrams)

Примечания:

• word_by_sorted.get("".join(sorted(xs)), set()) ищет отсортированную группу букв в виде строки в dict и возвращает набор слов или пустой набор , если не найдено совпадений.
• itertools.product(*L) создать декартово произведение найденных множеств. Если есть пустой набор (группа без совпадения), то продукт по определению пуст.

Ouput (есть причина для дубликатов, попробуйте найти ее!):

('nego', 'mal', 'toni')
('mal', 'nego', 'toni')
('mal', 'nego', 'toni')
('mal', 'nego', 'toni')

Здесь важно то, что количество слов больше не является проблемой (поиск в диктовке амортизируется O(1)), но длина текста для поиска может стать единицей.