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

Question

input: ['abc', 'cab', 'cafe', 'face', 'goo']
output: [['abc', 'cab'], ['cafe', 'face'], ['goo']]

Проблема проста: она группируется по анаграмм .Порядок не имеет значения.

Конечно, я могу сделать это на C ++ (это мой родной язык).Но мне интересно, что это можно сделать в одной строке по Python . РЕДАКТИРОВАНИЕ: Если это невозможно, возможно, 2 или 3 строки. Я новичок в Python.

Чтобы проверить, являются ли две строки анаграммой, я использовал сортировку.

>>> input = ['abc', 'cab', 'cafe', 'face', 'goo']
>>> input2 = [''.join(sorted(x)) for x in input]
>>> input2
['abc', 'abc', 'acef', 'acef', 'goo']

Я думаю, что это можно сделать, комбинируя map или около того.Но мне нужно использовать dict в качестве хеш-таблицы.Я еще не знаю, выполнимо ли это в одной строке.Любые намеки будут оценены!

Answer 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 function.

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

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

Answer 2

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

>>> 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']]

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

Answer 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']]

Answer 4

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

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

Answer 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, поскольку она объединяет только последовательные элементы, для которых ваша ключевая функция дает одинаковый результат.

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

Answer 6

Ответ Дейва лаконичен, однако сортировка, требуемая 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())