Поиск и группировка анаграмм Python

Ответ 1

Читаемое однострочное решение:

output = [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]

Например:

>>> words = ['abc', 'cab', 'cafe', 'goo', 'face']
>>> from itertools import groupby
>>> [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

Ключевое значение здесь - использовать itertools.groupby из модуля itertools, который будет группировать элементы в списке вместе.

Список, который мы поставляем в groupby, должен быть отсортирован в расширенном формате, поэтому мы передаем его sorted(words,key=sorted). Фокус здесь в том, что sorted может взять ключевую функцию и будет сортироваться на основе вывода этой функции, поэтому мы снова передаем sorted в качестве ключевой функции, и это будет сортировать слова, используя буквы строки, чтобы, Нет необходимости определять нашу собственную функцию или создавать lambda.

groupby использует ключевую функцию, которую он использует, чтобы указать, должны ли элементы группироваться вместе, и снова мы можем просто передать им встроенную функцию sorted.

Последнее, что нужно отметить, это выход из пары ключевых и групповых объектов, поэтому мы просто берем объекты группы и используем функцию list для преобразования каждого из них в список.

(BTW - я бы не назвал вашу переменную input, а затем скрыл встроенную функцию input, хотя она вероятно, не тот, который вы должны использовать.)

Ответ 2

не один вкладыш, а решение...

d = {}
for item in input:
  s = "".join(sorted(item))
  if not d.has_key(s):
    d[s] = []
  d[s].append(item)
input2 = d.values()

Ответ 3

Читаемая версия:

from itertools import groupby
from operator import itemgetter

def norm(w):
  return "".join(sorted(w))

words = ['abc', 'cba', 'gaff', 'ffag', 'aaaa']

words_aug = sorted((norm(word), word) for word in words)

grouped = groupby(words_aug, itemgetter(0))

for _, group in grouped:
  print map(itemgetter(1), group)

Однострочный:

print list(list(anagrams for _, anagrams in group) for _, group in groupby(sorted(("".join(sorted(word)), word) for word in words), itemgetter(0)))

Печать

[['aaaa'], ['abc', 'cba'], ['ffag', 'gaff']]

Ответ 4

нечитаемое однострочное решение:

>>> import itertools
>>> input = ['abc', 'face', 'goo', 'cab', 'cafe']
>>> [list(group) for key,group in itertools.groupby(sorted(input, key=sorted), sorted)]
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

(ну, это действительно 2 строки, если вы считаете импорт...)

Ответ 5

from itertools import groupby

words = ['oog', 'abc', 'cab', 'cafe', 'face', 'goo', 'foo']

print [list(g) for k, g in groupby(sorted(words, key=sorted), sorted)]

Результат:

[['abc', 'cab'], ['cafe', 'face'], ['foo'], ['oog', 'goo']]

Вы не можете просто использовать функцию groupby, так как это объединяет только последовательные элементы, для которых ваша ключевая функция дает тот же результат.

Простое решение состоит в том, чтобы сначала отсортировать слова, используя ту же функцию, что и для группировки.

Ответ 6

Ответ на Dave является кратким, однако сортировка, требуемая groupby, - это операция O(n log(n)). Более быстрым решением является следующее:

from collections import defaultdict

def group_anagrams(strings):
    m = defaultdict(list)

    for s in strings:
        m[tuple(sorted(s))].append(s)

    return list(m.values())