Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.53/30: Рейтинг темы: голосов - 30, средняя оценка - 4.53
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38

Анаграммы

08.02.2020, 11:14. Показов 6087. Ответов 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
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru