Нужно проверить количество анаграмм из введённых строк

Question

длинна строки всегда 10 символов, количество строк 2<=N<=10^5 пример ввода:

5 
abaaaaaaaa 
oneplustwo 
aaaaaaaaba 
twoplusone 
aaaabaaaaa

пример вывода:

то есть анаграммы: 1 и 3, 1 и 5, 3 и 5, 2 и 4 Я написал код но он слишком долго проверяет(нужно меньше 10 секунд) и выдаёт тайм эрор

anagrama = 0
koliczestvo = 0
list0 = []
for range1 in range(int(input())):
    b = input()
    list1 = list(b)
    list1.sort()
    list0.append(list1)
for range2 in range(len(list0)-1):
    for range3 in range(range2 + 1, len(list0)):
        if list0[range2] == list0[range3]:
            anagrama += 1
print(anagrama)

Помогите пожалуйста его упростить чтобы проверка проходила быстрее

Answer 1

Проблема в том, что алгоритм квадратичный: сравнивает каждый элемент с каждым. Я бы использовал для счета словарь или collections.Counter:

from collections import Counter

c = Counter()
for i in range(int(input())):
    line = input()
    c.update([''.join(sorted(line))])

print(sum(n * (n-1) // 2 for n in c.values()))

Последнее выражение основано на том, что в каждой группе нам надо посчитать анаграммы попарно, т.е. n * (n-1) / 2.

Answer 2

Можно заметить такую закономерность:

Анаграммы  | Пары
1            0
2            1  (+1)
3            3  (+2)
4            6  (+3)
5            10 (+4)
6            15 (+5)
7            21 (+6)
8            28 (+7)

И считать количество пар сразу после ввода:

dict = {}
total = 0

for i in range( int(input()) ):
    word = ''.join(sorted( input() ))

    val = dict.get(word, 0)
    ### Если ключ уже существует, .get() вернет его значение, иначе 0

    total += val
    dict[word] = val + 1

print( total )

БЛОГ НА HUSL

Нужно проверить количество анаграмм из введённых строк

Ответы (2 шт):