1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38

Анаграммы

08.02.2020, 11:14. Показов 6131. Ответов 39
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
number_of_words = int(input())
if number_of_words > 100000:
    exit(0)
 
words = []
anagrammbl = []
 
for i in range(number_of_words):  # добавить нужное кол-во слов в список
    words.append(input().lower())  # все слова маленькие
 
for i in words:
    result = []
    for j in words:
        if i != j:
            if sorted(list(i)) == sorted(list(j)):
                if i not in result:
                    result.append(i)
                result.append(j)
 
                words.remove(j)
    words.remove(i)
    anagrammbl.append(result)
 
if len(words) == 2:
    result = []
    if sorted(list(words[0])) == sorted(list(words[1])):
        result.append(words[0])
        result.append(words[1])
        anagrammbl.append(result)
 
anagrammbl = list(map(lambda x: sorted(x), anagrammbl))
anagrammbl.sort()
for i in anagrammbl:
    print(' '.join(i))
Этот код исправно работает, но бот не принимает его, из-за того, что он работает 4020 ms, а ограничение стоит на 4000ms.
Подскажите, как можно уменьшить время работы (Такое время работы, при условии, если я ищу анаграммы из 100000 слов)
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
08.02.2020, 11:14
Ответы с готовыми решениями:

Анаграммы
Есть такая несложная задача. Выписать все слова, которые являются анаграммами друг для друга, например «замок» и «мазок». Проверка...

Анаграммы
Задается словарь (список слов). Найти в нем все анаграммы (слова, составленные из одних и тех же букв).

Анаграммы
Анагра́мма (от греч. ανα- — «пере» и γράμμα — «буква») — литературный приём, состоящий в перестановке букв или звуков определённого слова...

39
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.02.2020, 11:25
А есть нормальная постановка задачи? Ограничения и т.д.
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 11:38  [ТС]
eaa, задача :
Вывести анаграммы слов. Т.е 1001 = 1001
Только в списке может быть 100 000 слов.
Проблема:
Боту не нравится время работы моей проги. Он хочет, чтобы я обработал 100 000 слов за 4 секунды (4000 ms)
А моя программа успевает только за (4020 ms)
Просьба:
Уменьшить время работы проги или сказать, что можно заменить
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 11:49
Можно пример ввода/вывода? Не совсем понимаю, нужно ли генерировать новые слова или искать существующие в списке.

Добавлено через 1 минуту
Кажется, нужно искать в существующих...

Добавлено через 4 минуты
Python
1
2
3
4
5
words = [input().lower() for _ in range(int(input()))]
for word in words:
    a = word[::-1]
    if a in words:
        print(f'{word} {a}')
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.02.2020, 11:52
задача на хэш
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 12:59  [ТС]
Рыжий Лис, Слова генерировать не нужно, к сожалению я не смогу сделать тебе пример вывода/ввода, т.к ввод - 100 000 строк, а вывод немного поменьше

Добавлено через 40 секунд
Рыжий Лис, мне нужно снизить работу программы минимум на 20ms, чтобы пройти проверку у бота

Добавлено через 43 минуты
eaa, нет
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 13:25
Цитата Сообщение от 3XTR4 Посмотреть сообщение
т.к ввод - 100 000 строк, а вывод немного поменьше
Да не конкретно этот пример, а хоть какой-нибудь. Строчки на 3-5.
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 13:26  [ТС]
Для тех, кто не понимает, что я вообще такое написал.
Мне просто нужно уменьшить время работы этого кода, но, я новичок, и не особо знаю все "тонкости" как ускорить кодец. Я понимаю, что можно убрать if len(words) == 2:, но тогда он работает неправильно, и по какой-то причине перескакивает то, что по идее он должен был давно вывести
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.02.2020, 13:36
модули какие нибудь использовать можно?
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 13:38
Чтобы понять как ускорить, нужно понять, что программа делает, чтобы сохранить наблюдаемое поведение. А вы который раз отказываетесь давать примеры ввода/вывода или объяснить словами что нужно вывести.

Добавлено через 40 секунд
Допустим, я ввёл следующее:
Code
1
2
3
4
3
fox
pony
xof
Что выведет программа?
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.02.2020, 13:55
и ограничения на вводимые слова бы понять.

Добавлено через 15 минут
Python
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
d = dict()
 
for _ in range(n):
    word = input().lower()
    word_sorted = ''.join(sorted(word))
    d.setdefault(word_sorted, []).append(word)
 
for k, v in d.items():
    if len(v) > 1:
        print(*v)
видимо еще нужно по ключу отсортировать.
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 15:50  [ТС]
eaa, Ограничений нет. Одна строка - одно слово. Ограничение только в кол-ве слов, а именно 100 000

Добавлено через 1 минуту
Рыжий Лис, fox xof (т.к это анаграммы (все буквы одного слова, есть в таком же количестве в другом слове)

Добавлено через 2 минуты
Рыжий Лис, "А вы который раз отказываетесь давать примеры ввода/вывода или объяснить словами что нужно вывести." Я не отказываюсь, а говорю, что никак не могу дать тебе 100 000 строк.
Пусть так:
Ввод:
11
окорок
петлей
Плетей
рококо
теплей
Тишь
ТОМНО
тонко
тонок
тоном
шить
Вывод :
окорок рококо
петлей плетей теплей
тишь шить
томно тоном
тонко тонок
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
08.02.2020, 15:58
3XTR4,
По слову "окорок" и "анаграмма" можно найти на форуме в разделе Python кучу тем с решениями.
Вы здесь 100500-ый кто не знает как правильно написать поиск анаграмм.
P.S. Не нужно называть своим темы вот так: "Нужно сократить время работы программы"
Тогда и подсказки внизу топика будут в тему.
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 16:00
Хм, и правда придётся строить подобие хеша...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
words = '''\
окорок
петлей
Плетей
рококо
теплей
Тишь
ТОМНО
тонко
тонок
тоном
шить'''.lower().split()
 
hashes = [''.join(sorted(i)) for i in words]
#print(hashes)
for word, hash in zip(words, hashes):
    print(word, *(w for w, h in zip(words, hashes) if h == hash))
Сложность О(n^2)
Code
1
2
3
4
5
6
7
8
9
10
11
окорок окорок рококо
петлей петлей плетей теплей
плетей петлей плетей теплей
рококо окорок рококо
теплей петлей плетей теплей
тишь тишь шить
томно томно тоном
тонко тонко тонок
тонок тонко тонок
тоном томно тоном
шить тишь шить
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
08.02.2020, 16:00
del
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 16:02  [ТС]
Garry Galler, Garry
1-ых : он уже написан
2-ых : исправно работает
3-их : я всего лишь хочу узнать, что не так в моём коде, мне не хватает всего жалких 20-10ms, чтобы бот принял моё решение.
Цитата Сообщение от 3XTR4 Посмотреть сообщение
Этот код исправно работает, но бот не принимает его, из-за того, что он работает 4020 ms, а ограничение стоит на 4000ms.
Подскажите, как можно уменьшить время работы
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 16:04
Цитата Сообщение от 3XTR4 Посмотреть сообщение
if sorted(list(i)) == sorted(list(j)):
Например, это вынести из цикла и считать один раз. Точно будет на 20 мс быстрее.
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 16:09  [ТС]
Цитата Сообщение от Garry Galler Посмотреть сообщение
P.S. Не нужно называть своим темы вот так: "Нужно сократить время работы программы"
Тема - отражает то, что мне нужно. Я сделал код, он работает, но бот его не проверяет из-за времени работы (опять же повторяюсь 100-й раз). Вот я и спрашиваю, какое место в коде можно оптимизировать, чтобы вписаться в рамки

Добавлено через 2 минуты
Цитата Сообщение от Рыжий Лис Посмотреть сообщение
if sorted(list(i)) == sorted(list(j)):
Например, это вынести из цикла и считать один раз. Точно будет на 20 мс быстрее.
К сожалению, это обязательно нужно. Так как слово "окорок" и "рококо" предстанут перед этим условием ввиде :
['к', 'к', 'о', 'о', 'о', 'р']
['к', 'к', 'о', 'о', 'о', 'р'] => слова анаграммы => добавить их в список anagrammbl
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.02.2020, 16:09
3XTR4, я написал Вам решение. смотрите выше.
1
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 16:13
Не, смотри:
Python
1
2
3
4
5
6
7
8
9
10
hd, hl = {}, []
for w in words:
    h = ''.join(sorted(w))
    hd.setdefault(h, []).append(w)
    hl.append(h)
for w, h in zip(words, hl):
    l = hd[h]
    l.remove(w)
    if l:
        print(w, *l)
Отдельно храним слова и их "хеш" (['к', 'к', 'о', 'о', 'о', 'р']), чтобы считать "хеш" только один раз. А итерироваться одновременно по двум спискам можно через zip

Добавлено через 1 минуту
Будет как-то так:
Python
1
2
3
4
5
6
7
8
9
10
11
12
for i, h1 in zip(words, hashes):
    result = []
    for j, h2 in zip(words, hashes):
        if i != j:
            if h1 == h2:
                if i not in result:
                    result.append(i)
                result.append(j)
 
                words.remove(j)
    words.remove(i)
    anagrammbl.append(result)
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
08.02.2020, 16:13
Помогаю со студенческими работами здесь

Игра Анаграммы
Хочу сделать так чтобы во время просьбы о подсказке при нажатии "нет" выходило из игры, пробовал сам - не вышло Помогите оптимизировать...

Ох уж эти анаграммы
Задача Анагра́мма (от греч. ανα- — «пере» и γράμμα — «буква») — литературный приём, состоящий в перестановке букв или звуков...

Ох уж эти анаграммы
number_of_words = int(input()) # количество слов if number_of_words > 100000: exit(0) words = set() # слова, без повторений. ...

Найти все слова - анаграммы
Ваша задача — выписать все слова, которые являются анаграммами друг для друга, например «замок» и «мазок». Проверка слов должна быть...

Игра анаграммы. Майкл Доусон "Программируем на Python". Глава 4
Добрый день! Задача: доработать игру "Анаграммы" из указанного учебника так, чтобы к каждому слову полагалась подсказка. Игрок должен...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

Новые блоги и статьи
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка SDL3 и Box2D из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru