Поиск и группировка анаграмм по Python - PullRequest
Новая
       3

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

3 голосов
/ 18 ноября 2011 
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 в качестве хеш-таблицы.Я еще не знаю, выполнимо ли это в одной строке.Любые намеки будут оценены!

Ответы [ 6 ]

6 голосов
/ 18 ноября 2011

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

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 функцию , хотя, вероятно, вам не следует использовать ее.)

3 голосов
/ 18 ноября 2011

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

>>> 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 голосов
/ 18 ноября 2011

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

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']]
2 голосов
/ 18 ноября 2011

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

d = {}
for item in input:
  s = "".join(sorted(item))
  if not d.has_key(s):
    d[s] = []
  d[s].append(item)
input2 = d.values()
1 голос
/ 18 ноября 2011 
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, поскольку она объединяет только последовательные элементы, для которых ваша ключевая функция дает одинаковый результат.

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

0 голосов
/ 03 июня 2017

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