Я пытаюсь выяснить, почему моя функция анаграммы получает неправильный вывод - PullRequest
Новая
       28

Я пытаюсь выяснить, почему моя функция анаграммы получает неправильный вывод

0 голосов
/ 27 апреля 2020

Параметр представляет собой список слов. Требуемый вывод списка сгруппированных анаграмм. 

def anagrams(lst):
    d = {}
    while len(lst) > 0:
        pop = lst.pop()
        d[pop] = d.get(pop, [])
        d[pop].append(pop)
        for word in lst:
            perm = [''.join(p) for p in permutations(pop)]
            if word in perm:
                d[pop].append(word)
                lst.remove(word)
    anagram = d.values()
    return list(anagram)

print(anagrams(['eat', 'ate', 'done', 'tea', 'soup', 'node']))

--- Консольный вывод ... (неправильный вывод) --- 

 [['node', 'done'], ['soup'], ['tea', 'eat'], ['ate']]

--- Желаемый вывод --- 

 [['eat', 'ate', 'tea], ['done', 'node'], ['soup']]

Вещи, которые я пробовал Мой псевдокод, когда pop = 'tea' в то время как l oop

pop = ‘tea’
lst = [‘eat’,’ate’]

for ‘eat’ in lst:
    perm = perm of [tea]
    if eat in perm (true)
        d[tea].append(‘eat’)  # d[tea] = [tea, eat]
        lst = [‘ate’]

for ‘ate’ in lst:
    perm = perm of [tea]
    if ‘ate’ in perm: (should be yes)
        d[tea].append(ate) -> d[tea] = [tea, eat, ate]
        lst.remove['ate'] -> lst = []

Это не так

Ответы [ 2 ]

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

Более простое решение из здесь 

def anagrams(strs):
  result = {}
  for i in strs:
      x = "".join(sorted(i))
      result.setdefault(x, []).append(i)
  return list(result.values())

print(anagrams(['eat', 'ate', 'done', 'tea', 'soup', 'node']))

#Out: [['eat', 'ate', 'tea], ['done', 'node'], ['soup']]

Объяснение

Ссылка

Чтобы решить эту проблему, мы будем следовать этим шагам 

Define result as map 

for i in string array
   x := x and join, sorted string of i 
   if x in result 
     insert i in result[x] 
   else result[x] := [i] 

return values of result as list
1 голос
/ 27 апреля 2020

Я думаю, у вас есть правильная идея, но вы делаете это слишком сложно. Вы можете создать свой словарь так, чтобы ключи были отсортированными буквами слова. Это приведет к тому, что ate и eat оба окажутся в одном месте под ключом aet. При этом вы избегаете вычисления перестановок, это всего лишь пара строк, и это быстро: 

from collections import defaultdict

def anagrams(words):
    lookup = defaultdict(list)
    for word in words:
        lookup["".join(sorted(word))].append(word)
    return list(lookup.values())


anagrams(['eat', 'ate', 'done', 'tea', 'soup', 'node'])
# [['eat', 'ate', 'tea'], ['done', 'node'], ['soup']]
...