Ю12.19

Задача:  В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть перестановкой, например, (КОРМА, КОМАР).

Код:

 

Тесты:

Исходный словарь Обработанный словарь
the and a to I is of have you he it in not was that his do on with she at say her for as are we but can him they up what out me go get this from be look my there know all one no see will back into like if were then an come think so down your them would about man take just by am now over make been or time when hand who want here tell off right their turn two through eye head other how some more around door room face day where way night well thing open away give only something ask move stand good find again little try too still hear walk before leave sit let long call feel close very why which car any hold work run never start even light than after put yes stop old watch first may talk another cut mean pull behind smile our toward towards much its house keep place begin nothing year woman side because three seem wait need moment himself stare arm use voice last late across sure front sound big really name should new anything against guy kill point small happen wall black step window life maybe fall own far under boy

no
on
three
there
own
now
how
who
thing
night
its
sit
name
mean

Все слова Безымянный

Алгоритм:

Для решения данной задачи я воспользовался возможностью, которую мне предоставляет библиотека <algorithm> . Поскольку мне надо было проверить, являются ли строки перестановками строки s_tmp, которую я ставлю в роли исходной с каждой итерацией, я воспользовался функцией is_permutation .  Если некая строка является перестановкой, то она выводится на экран и стирается. С последующими итерациями будет проводится проверка на наличие на том или ином месте строки. Если строки обнаружено не будет, программа перейдёт к следующей итерации.

Для проверки правильности работы программы, воспользуйтесь ссылкой .

UPD: Поскольку я понял, что вводить вначале количество слов неудобно, я решил написать функцию, которая сама создаст массив из введённой мной строкой.

Марченко Філіп Олександрович
Марченко Філіп Олександрович

Latest posts by Марченко Філіп Олександрович (see all)

3 thoughts on “Ю12.19

  1. — Посмотрите, пожалуйста, здесь почти в конце перед видеолекциями должен быть словарь английских слов.
    — И сюда нужно заглянуть.
    — clear() не очищает память. Длине строки присваивается значение 0, но capacity не изменяется и все символы строки остаются в памяти.
    — Пожалуйста, печатайте только те группы слов, где их больше одного. Каждую группу с новой строки.

    • Исправлено. C-string выложу позже.
      Насчёт теста «Все слова»: работало долго, дымясь, пыхтя и проклиная меня, но выдало ответ.

  2. — Добавьте в метки слово «анаграмма».
    — В 62-й строке лучше пробел, чем новая строка. Анаграммы будут в отдельной строке.
    — Ещё один небольшой недочёт — если встречаются одинаковые слова их не стоит считать анаграммой.
    — Основная проблема. Программа не успевает за 15 секунд отработать словарь из ~2500 слов. Это нереально долго. Для проверки я написал простой код с квадратичной сложностью по числу слов. Он успевает. Используйте его для тестирования если нужно. Но программа должна успеть обработать все данные из тестового словаря.

    Выполнить
    Существенно ускорить (до n*log(n)) можно при помощи специальной сортировки. Нужно составить алгоритм компаратора, который сравнивает строки по числу использованных букв. Самый простой способ сделать это — отсортировать буквы в словах. После сортировки по отсортированным словам (забавно звучит!), все анаграммы окажутся рядом. Это добавит несколько строк кода, но программа будет существенно быстрее:

    Выполнить
    Дальнейшее сокращение времени работы программы потребует дополнительной памяти для хранения сортированных побуквенно слов в виде ключей к обычным словам (т.е. структур вида key=>value).

Добавить комментарий