Анаграммы

@3XTR4 · Регистрация: 04.11.2019

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 слов)

@3XTR4 · 08.02.2020, 16:14 **[ТС]**

eaa, Я заметил, спасибо. Насколько я понял, мой код получился слишком..... громоским?
Твоё решение мне нравится, не мог бы объяснить, как оно работает?

@Garry Galler · 08.02.2020, 16:21

Сообщение от 3XTR4

что не так в моём коде,

Никому неинтересно объяснять почему говнокод - говнокод.
Решение eaa уже приводилось в аналогичной теме.

@3XTR4 · 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]

Рыжий Лис · 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

Тоже метод словаря, который работает не совсем очевидно.

@3XTR4 · 08.02.2020, 16:31 **[ТС]**

Сообщение от Рыжий Лис

if len(words) == 2:
Странная магия, без которой не работает.

Согласен, у меня тоже был вопрос. Почему оставшийся список например : [томно, номот] не являются анаграммами, поэтому и пришлось такую абракадабру писать.

Сообщение от Рыжий Лис

Странная магия, без которой не работает.

Как ты и сказал "странная магия"

Добавлено через 1 минуту

Сообщение от Рыжий Лис

words.remove(i)
Опасно удалять элементы из списка, по которому итерируемся.

Будет перескакивать/пропускать элементы, или есть ещё другие причины?

@eaa · 08.02.2020, 16:34

Я бы вообще написал свою хэш-функцию. Потом отсортировал по ней, далее GroupBy. Но увы ограничений и точной формулировки не услышал...
А ТС совет учить структуры данных.

@3XTR4 · 08.02.2020, 16:36 **[ТС]**

Сообщение от eaa

А ТС совет учить структуры данных.

Ок, учту

Добавлено через 1 минуту

Сообщение от eaa

Я бы вообще написал свою хэш-функцию. Потом отсортировал по ней, далее GroupBy. Но увы ограничений и точной формулировки не услышал...

Ограничение - одно слово на одну строку, не более 100 000 строк.
На этом всё, больше ограничений и т.п нет

Рыжий Лис · 08.02.2020, 16:42

Сообщение от 3XTR4

а этом всё, больше ограничений и т.п нет

Порядок вывода ещё интересует. Если важен, то код чуть усложняется: Анаграммы

Добавлено через 27 секунд

Сообщение от 3XTR4

Будет перескакивать/пропускать элементы, или есть ещё другие причины?

Ага

@3XTR4 · 08.02.2020, 16:47 **[ТС]**

Рыжий Лис, порядок вывода для строк и для слов лексиграфический

Рыжий Лис · 08.02.2020, 16:49

Значит можно взять программу eaa и отсортировать списки в двух местах (строки и слова в строках).

@eaa · 08.02.2020, 17:00

Потом выяснится что слова в списке могут повторяться и т.п. Что нужно было брать set, а не list.

Рыжий Лис · 08.02.2020, 17:09

На set-то переделать недолго.

Добавлено через 1 минуту
Или вообще изначально отфильтровать список слов:

Python
1
words = list(set(words))

@Semen-Semenich · 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 минуты
проверил, нужно будет убрать те ключи где только одно слово в списке а это увы лишний цикл фильтра, проверка длины, вообщем вряд ли прокатит

@3XTR4 · 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-ой строки
окорок рококо
шить тишь
тонок тонко

Рыжий Лис · 09.02.2020, 08:31

Ага, косяк:

Python
1
l = hd[h].copy()

Добавлено через 3 минуты

Code
1
2
3
4
5
окорок рококо
петлей плетей теплей
плетей петлей теплей
рококо окорок
теплей петлей плетей

@Semen-Semenich · 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 )

==
окорок рококо
петлей плетей теплей
тишь шить
томно тоном
тонко тонок
>>>

@3XTR4 · 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)

Не решение, потому что этот код может вывести одну и ту же букву как анаграмму, или одно и тоже слово. А так нельзя

Рыжий Лис · 10.02.2020, 10:14

Код не мой, так что претензии не ко мне

@eaa · 10.02.2020, 10:21

А я уже писал:

Сообщение от eaa

Потом выяснится что слова в списке могут повторяться и т.п. Что нужно было брать set, а не list.

задачи надо ставить четко

Рыжий Лис · 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)

Новые блоги и статьи Все статьи Все блоги /
24 Мат модель здравосохранения: функциональные требования к строительству пищеблока anaschu 18.06.2026 СРесурсами1: финансовый SD-контур, калькулятор функциональных требований пищеблока Сегодня разделили затраты в агенте Экономика по образцу модели НАСОСЫ, добавили расчёт ROI и построили первый. . .	23. что сделано за последнее время. anaschu 17.06.2026 • Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .	22. Подключение слоя системной динамики (потоковые диффуры): экономические метрики модели anaschu 17.06.2026 Апдейт модели: финансовый контур, разделение затрат Продолжаю развивать модель рабочего коллектива на AnyLogic. В этот раз работа шла над агентом Экономика — финансовым SD-слоем модели. Задача:. . .	[golang] Insert Delete GetRandom O(1) (Leetcode: 380) alhaos 16.06.2026 Insert Delete GetRandom O(1) Сложность: Medium Источник: LeetCode 380 Задача Реализовать структуру данных RandomizedSet, которая поддерживает следующие операции за O(1) в среднем:
Свет в конце тоннеля kumehtar 16.06.2026 Поймал себя на одной мысли. Раньше мне всегда казалось неправильным жить без чёткого понимания, куда всё идёт. Будто я иду по дороге судьбы, но не знаю, куда она ведёт. А раз не знаю — значит,. . .	[golang] Реализация стека с поддержкой получения минимального элемента за O(1) alhaos 16.06.2026 Min Stack Сложность: Medium Источник: LeetCode 155 Задача: Реализовать стек который поддерживает push, pop, top и получение минимального элемента за O(1). Методы:	[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .

@3XTR4 1 / 1 / 0 Регистрация: 04.11.2019 Сообщений: 38
	08.02.2020, 16:14 [ТС]
	eaa, Я заметил, спасибо. Насколько я понял, мой код получился слишком..... громоским? Твоё решение мне нравится, не мог бы объяснить, как оно работает? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	08.02.2020, 16:34
	Я бы вообще написал свою хэш-функцию. Потом отсортировал по ней, далее GroupBy. Но увы ограничений и точной формулировки не услышал... А ТС совет учить структуры данных. 0

@3XTR4 1 / 1 / 0 Регистрация: 04.11.2019 Сообщений: 38
	08.02.2020, 16:47 [ТС]
	Рыжий Лис, порядок вывода для строк и для слов лексиграфический 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	08.02.2020, 16:49
	Значит можно взять программу eaa и отсортировать списки в двух местах (строки и слова в строках). 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	08.02.2020, 17:00
	Потом выяснится что слова в списке могут повторяться и т.п. Что нужно было брать set, а не list. 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	10.02.2020, 10:14
	Код не мой, так что претензии не ко мне 0