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

Анаграммы

08.02.2020, 11:14. Показов 6244. Ответов 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
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 16:14  [ТС]
Студворк — интернет-сервис помощи студентам
eaa, Я заметил, спасибо. Насколько я понял, мой код получился слишком..... громоским?
Твоё решение мне нравится, не мог бы объяснить, как оно работает?
0
Эксперт Python
5439 / 3860 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
08.02.2020, 16:21
Цитата Сообщение от 3XTR4 Посмотреть сообщение
что не так в моём коде,
Никому неинтересно объяснять почему говнокод - говнокод.
Решение eaa уже приводилось в аналогичной теме.
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 16:24  [ТС]
eaa, Твоё решение мне понравилось.
Не мог бы объяснить, как работает код
Цитата Сообщение от eaa Посмотреть сообщение
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)
?


Как я это вижу.

Мы вводим число и спрашиваем сколько раз нам зададут слова
Создали множество

Потом пошёл цикл, в котором добавляем слова в нижнем регистре
Сортируем, по алфавиту (стандартно)

Python
1
d.setdefault(word_sorted, []).append(word)
^
Момент не понятен L
Python
1
for k, v in d.items():
Откуда взялись k, v (скорее всего это как i in list),что это за items?

И дальше не особо понятно
Python
1
2
if len(v) > 1:
        print(*v)[/quote]
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 16:27
Цитата Сообщение от Garry Galler Посмотреть сообщение
Никому неинтересно объяснять почему говнокод - говнокод.
Почему же.

1)
Цитата Сообщение от 3XTR4 Посмотреть сообщение
words.remove(i)
Опасно удалять элементы из списка, по которому итерируемся.

2)
Цитата Сообщение от 3XTR4 Посмотреть сообщение
if sorted(list(i)) == sorted(list(j)):
Уже писал, можно вынести из цикла и посчитать один раз.

3)
Цитата Сообщение от 3XTR4 Посмотреть сообщение
if len(words) == 2:
Странная магия, без которой не работает.

Ну и неудачно выбранный алгоритм (полный перебор списков), дающий сложность О(n^2) и выше.

Добавлено через 33 секунды
Цитата Сообщение от 3XTR4 Посмотреть сообщение
это за items?
Метод словаря.

Добавлено через 57 секунд
Цитата Сообщение от 3XTR4 Посмотреть сообщение
d.setdefault
Тоже метод словаря, который работает не совсем очевидно.
1
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 16:31  [ТС]
Цитата Сообщение от Рыжий Лис Посмотреть сообщение
if len(words) == 2:
Странная магия, без которой не работает.
Согласен, у меня тоже был вопрос. Почему оставшийся список например : [томно, номот] не являются анаграммами, поэтому и пришлось такую абракадабру писать.
Цитата Сообщение от Рыжий Лис Посмотреть сообщение
Странная магия, без которой не работает.
Как ты и сказал "странная магия"

Добавлено через 1 минуту
Цитата Сообщение от Рыжий Лис Посмотреть сообщение
words.remove(i)
Опасно удалять элементы из списка, по которому итерируемся.
Будет перескакивать/пропускать элементы, или есть ещё другие причины?
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.02.2020, 16:34
Я бы вообще написал свою хэш-функцию. Потом отсортировал по ней, далее GroupBy. Но увы ограничений и точной формулировки не услышал...
А ТС совет учить структуры данных.
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 16:36  [ТС]
Цитата Сообщение от eaa Посмотреть сообщение
А ТС совет учить структуры данных.
Ок, учту

Добавлено через 1 минуту
Цитата Сообщение от eaa Посмотреть сообщение
Я бы вообще написал свою хэш-функцию. Потом отсортировал по ней, далее GroupBy. Но увы ограничений и точной формулировки не услышал...
Ограничение - одно слово на одну строку, не более 100 000 строк.
На этом всё, больше ограничений и т.п нет
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 16:42
Цитата Сообщение от 3XTR4 Посмотреть сообщение
а этом всё, больше ограничений и т.п нет
Порядок вывода ещё интересует. Если важен, то код чуть усложняется: Анаграммы

Добавлено через 27 секунд
Цитата Сообщение от 3XTR4 Посмотреть сообщение
Будет перескакивать/пропускать элементы, или есть ещё другие причины?
Ага
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
08.02.2020, 16:47  [ТС]
Рыжий Лис, порядок вывода для строк и для слов лексиграфический
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 16:49
Значит можно взять программу eaa и отсортировать списки в двух местах (строки и слова в строках).
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.02.2020, 17:00
Потом выяснится что слова в списке могут повторяться и т.п. Что нужно было брать set, а не list.
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
08.02.2020, 17:09
На set-то переделать недолго.

Добавлено через 1 минуту
Или вообще изначально отфильтровать список слов:
Python
1
words = list(set(words))
0
 Аватар для Semen-Semenich
5239 / 3483 / 1176
Регистрация: 21.03.2016
Сообщений: 8,313
08.02.2020, 19:03
такой вариант интересно пройдет?
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
words = '''\
окорок
петлей
Плетей
рококо
теплей
Тишь
ТОМНО
тонко
тонок
тоном
шить'''.lower().split()
 
dct = {}
for i in words:
    dct.setdefault(''.join(sorted(i)),[]).append(i)
for i in dct.values():
    print(*i)
==
окорок рококо
петлей плетей теплей
тишь шить
томно тоном
тонко тонок
>>>

Добавлено через 4 минуты
проверил, нужно будет убрать те ключи где только одно слово в списке а это увы лишний цикл фильтра, проверка длины, вообщем вряд ли прокатит
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
09.02.2020, 07:25  [ТС]
Цитата Сообщение от Semen-Semenich Посмотреть сообщение
вообщем вряд ли прокатит
Ты прав. Не прокатит, потому что такой код подойдёт только для этого примера, для других - нет

Добавлено через 3 часа 49 минут
Цитата Сообщение от Рыжий Лис Посмотреть сообщение
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)
В таком коде есть один нюанс, из-за которого я и удалял элементы из списка, по которому итерируемся.
Мы выводим
плетей теплей петлей
томно тоном
теплей петлей <-- будто вырвано из 1-ой строки
окорок рококо
шить тишь
тонок тонко
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
09.02.2020, 08:31
Ага, косяк:
Python
1
l = hd[h].copy()
Добавлено через 3 минуты
Code
1
2
3
4
5
окорок рококо
петлей плетей теплей
плетей петлей теплей
рококо окорок
теплей петлей плетей
0
 Аватар для Semen-Semenich
5239 / 3483 / 1176
Регистрация: 21.03.2016
Сообщений: 8,313
09.02.2020, 08:32
можно просто проверять и если нет элемента в значении то только тогда добавлять. как по времени будет работать нужно проверять
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
words = '''\
окорок петлей Плетей
рококо теплей Тишь
ТОМНО тонко тонок
тоном томак рококо
тоном рококо теплей
окорок петлей Плетей
рококо теплей Тишь
ТОМНО тонко тонок
тоном томак рококо
тоном рококо теплей
шить шток маг'''.lower().split()
 
dct = {}
for i in words:
    key = ''.join(sorted(i))
    list_val = dct.setdefault(key,[])
    if i not in list_val:
        list_val.append(i)
    dct[key] = list_val
    
for i in filter(lambda x : len(x) > 1,dct.values()):
    print(*i )
==
окорок рококо
петлей плетей теплей
тишь шить
томно тоном
тонко тонок
>>>
0
1 / 1 / 0
Регистрация: 04.11.2019
Сообщений: 38
10.02.2020, 07:25  [ТС]
Рыжий Лис,
Цитата Сообщение от eaa Посмотреть сообщение
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
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
10.02.2020, 10:14
Код не мой, так что претензии не ко мне
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
10.02.2020, 10:21
А я уже писал:
Цитата Сообщение от eaa Посмотреть сообщение
Потом выяснится что слова в списке могут повторяться и т.п. Что нужно было брать set, а не list.
задачи надо ставить четко
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
10.02.2020, 10:23
Если слова повторяются, то используем set вместо списка:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
words = list(sorted(set(words)))
 
hd, hl = {}, []
for w in words:
    h = ''.join(sorted(w))
    hd.setdefault(h, set()).add(w)
    hl.append(h)
 
for h, w in hd.items():
    hd[h] = sorted(w)
 
for h, w in zip(hl, words):
    l = hd[h].copy()
    l.remove(w)
    if l:
        print(w, *l)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
10.02.2020, 10:23

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

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

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

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

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


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

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

Новые блоги и статьи
сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато
anaschu 11.07.2026
Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .
Сукцессия 20. Война автоботов. Делаем ставки. Лёд против "пш-пш!".
anaschu 11.07.2026
Битва ИИ в ризосфере: Как мы скрестили жесткие ОДУ, закон Фика и «подземный шантаж» Уважаемые коллеги! Хочу поделиться уникальным опытом ведения междисциплинарной компьютерной разработки. Прямо. . .
Сукцессия 19. Какие выводы я сделал из модели? Часть 2.Внутримикоризный стехиометрический буфер и хроно-дискретные зоны экспансии
anaschu 11.07.2026
Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования
Сукцессия 18. Какие выводы я сделал из войны грибов с деревьями? Часть 1- рассказ и немного про термины
anaschu 11.07.2026
Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования Система ОДУ описывает динамику изменения массы различных компонентов системы во времени. Ключевой. . .
Просветление в 5 секунд
kumehtar 10.07.2026
Андрей Веретенников выдал фразу недавно: "Вам не обязательно кем-то себя считать"
Эксперимент с картинкой-обложкой на CodinGame
Adler 10.07.2026
Решил на днях провести эксперимент. У меня есть аккаунт на CodinGame, ТОП-3 по РФ среди 2200 участников (в разделе соревнования по программированию ИИ-ботов). Там есть обложка, куда можно влепить. . .
GitDOS: Когда я решил скрестить MS-DOS, GitHub и Claude
MaGz GoLd 08.07.2026
Привет, Киберфорум! Хочу поделиться своим проектом, который, надеюсь, вас заинтересует. GitDOS — это веб-приложение, которое позволяет запускать DOS в браузере с тремя крутыми фичами: диски живут в. . .
Учебный мини "цифровой двойник" = (Сервер = Java + Flask_питон )+(3D = Гугловскаая 4T nvideo + google colab) +( WMS = Odoo на Docker)
anaschu 07.07.2026
Увидел в требованиях к вакансии создателя имитационных моделей связку (REst + Api + WMS + Anylogic + питон + 3D Nvideo), и решил посмотреть, что это такое. Из этого всего я работал более менее. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru