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

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

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

Конечно, я могу сделать это на C ++ (это мой родной язык). Но, мне интересно, что это можно сделать в одной строке Python . EDITED: Если это невозможно, возможно, 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 Solutions collect form web for “Поиск и группировка анаграмм Python”

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

 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 , хотя, вероятно, это не тот, который вы должны использовать.)

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

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

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

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

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

 >>> 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 строки, если вы считаете импорт …)

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

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

Ответ Дэйва groupby , однако сортировка, требуемая groupby является 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()) 
  • Как удалить смежные повторяющиеся элементы в списке, используя списки?
  • Элегантный способ получить hashtags из строки в Python?
  • фильтрация элементов из списка списков в Python?
  • Python, работающий со списком
  • Есть ли лучший способ конвертировать список в словарь в Python с ключами, но нет значений?
  • Поиск простых чисел с использованием списка
  • Что означает «понимание списка»? Как это работает и как я могу его использовать?
  • Расширение кортежей в генераторе понимания списка
  •  
    Interesting Posts for Van-Lav

    Понимание политики python для поиска минимума в списке списка

    Ошибка кодирования при десериализации объекта json от Google

    Эквивалент Builder в Python

    Pretty print namedtuple

    Смутно о параметрах package_dir и пакетах в файле setup.py

    С помощью Flask Blueprints, как исправить url_for от взлома, если указан субдомен?

    Мне нужна помощь, обертывающая мою голову вокруг оператора return с помощью Python и его роли в этом рекурсивном выражении

    Тензорный поток: что такое tf.contrib? И где я могу найти исходный код для `tf.contrib.layers.sparse_column_with_hash_bucket`?

    Заменить четырехсловное слово в python

    Python 2.7 на App Engine, simplejson vs native json, кто быстрее?

    Является ли API-интерфейс python полностью совместимым с C ++?

    Почему символ «{» остается, когда f "\ {10}" оценивается в Python 3.6?

    PhantomJS 1.8 с селеном на питоне. Как заблокировать изображения?

    логарифмически разнесенные целые числа

    Loop печатает через два списка, чтобы получить два столбца с фиксированным (настраиваемым набором) пробелом между первой буквой каждого элемента каждого списка

    Python - лучший язык программирования в мире.