Python 3: очень сложная (по крайней мере для меня) домашняя работа в университете об анаграммах - PullRequest
Новая
       28

Python 3: очень сложная (по крайней мере для меня) домашняя работа в университете об анаграммах

2 голосов
/ 26 апреля 2020

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

У меня есть список строк, где каждое слово является анаграммой некоторых других, которые мы называем «генератором». Для каждого «генератора» связанные строки могут быть его анаграммами или анаграммами + 1 буква. Мне нужно найти «генератор» с максимальным количеством связанных слов.

Пример объясняет лучше:

Строки:

  • трота
  • tratto
  • arto
  • parto
  • таро
  • тротта
  • ротта
  • орта
  • porta

"генератор" с максимальным количеством слов: ' arto ' (или его анаграмма) и связанные слова:

  • arto
  • orta (анаграммы 'arto')
  • parto (анаграммы 'arto' + буква p)
  • porta (анаграммы 'arto' + буква p )
  • ротта (анаграммы 'arto' + буква t)
  • таро (анаграммы 'arto')
  • трота (анаграммы 'arto' + буква t)

исключены слова "tratto" и "trotta", потому что они слишком длинные.

возможно, что "генератор" не включен в конечный результат, пример:

  • beel
  • baee
  • beae

The " генератор "is ' пчела '

Это мое решение: 

def open_r(ftesto_in):
    lista = []
    with open(ftesto_in, encoding='utf8') as f:
        for word in f:
            lista.append(word.strip())
    return lista

def es(ftesto_in):
    lista=open_r(ftesto_in)
    d = {}
    for i in range(len(lista)):
        a = lista[i]
        for j in range(i+1, len(lista)):
            b = lista[j]
            if len(a) == len(b) or len(a) == len(b)+1 or len(a) == len(b)-1:
                    gen = tuple(generator(a,b))
                    if len(gen) == len(a) or len(gen) == len(a)-1:
                        dic_upd(d, gen, a)
                    if len(gen) == len(b) or len(gen) == len(b)-1:
                        dic_upd(d, gen, b)                           
    d = {k: list(set(v)) for k, v in d.items()}
    result = maximum(d)
    return result

def dic_upd(d,k,v):
    if k not in d:
        d[k] = [v]
    else:
        d[k].append(v)

def maximum(d):
    result = 0
    lista = []
    for k,v in d.items():
        count = len(v)
        if count > result:
            result = count
            lista.clear()
            for i in v:
               lista.append(i)
    return lista


def generator(a,b):
    res = []
    a = list(a)
    b = list(b)
    for i in a:
        if i in b:
            res.append(i)
            b.remove(i)
    return sorted(res)

, когда число строк превышает 2-3 сотни или строки очень длинные Моя программа занимает много секунд или минут. У вас есть идея, как найти эти слова? Спасибо!

1 Ответ

1 голос
/ 26 апреля 2020

Подсказка: подсчитайте количество вхождений каждого символа в вашем вводе для каждого слова. Вы можете эффективно решить проблему, используя только это? Например: 

        a  o  p  r  t
trota   1  1  0  1  2
tratto  1  1  0  1  3
arto    1  1  0  1  1
parto   1  1  1  1  1
taro    1  1  0  1  1
trotta  1  1  0  1  3
rotta   1  1  0  1  2
orta    1  1  0  1  1
porta   1  1  1  1  1
...