Grouping

Grouping — это приём, когда мы раскладываем элементы по группам на основе
какого-то признака.

То есть мы не просто считаем:

элемент -> сколько раз встретился

как в frequency map, а собираем:

ключ группы -> список элементов этой группы

Допустим, есть слова:

["eat", "tea", "tan", "ate", "nat", "bat"]

Мы хотим сгруппировать анаграммы.

У слов "eat", "tea", "ate" одинаковые буквы. Если отсортировать буквы, у
всех получится один ключ:

eat -> aet
tea -> aet
ate -> aet

У "tan" и "nat":

tan -> ant
nat -> ant

Получается grouping:

aet -> ["eat", "tea", "ate"]
ant -> ["tan", "nat"]
abt -> ["bat"]

То есть мы создаём группы по общему признаку.

Базовый паттерн

groups = {}

for item in items:
    key = get_group_key(item)

    if key not in groups:
        groups[key] = []

    groups[key].append(item)

Главная мысль:

для каждого элемента вычислить ключ группы
и положить элемент в соответствующий список

Пример: grouping по длине слова

words = ["cat", "dog", "apple", "sun", "banana"]

groups = {}

for word in words:
    key = len(word)

    if key not in groups:
        groups[key] = []

    groups[key].append(word)

print(groups)

Результат:

3 -> ["cat", "dog", "sun"]
5 -> ["apple"]
6 -> ["banana"]

Здесь ключ группы — длина слова.

Пример: group anagrams

Для группировки анаграмм ключом можно сделать отсортированные буквы слова.

const words = ["eat", "tea", "tan", "ate", "nat", "bat"];
const groups = new Map();

for (const word of words) {
  const key = word.split("").sort().join("");

  if (!groups.has(key)) {
    groups.set(key, []);
  }

  groups.get(key).push(word);
}

console.log([...groups.values()]);
// [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Пример в Java

Map<Integer, List<String>> groups = new HashMap<>();

for (String word : words) {
    int key = word.length();

    groups
        .computeIfAbsent(key, k -> new ArrayList<>())
        .add(word);
}

Это очень типичный алгоритмический паттерн:

Map<Key, List<Value>>

Например:

Map<Integer, List<String>> wordsByLength;
Map<String, List<String>> anagramsBySortedLetters;
Map<Integer, List<User>> usersByAge;
Map<String, List<Order>> ordersByCustomerId;

Чем grouping отличается от frequency map

Frequency map:

ключ -> количество

Пример:

apple -> 3
banana -> 2
orange -> 1

Grouping:

ключ -> список элементов

Пример:

3 буквы -> ["cat", "dog", "sun"]
5 букв -> ["apple"]
6 букв -> ["banana"]

То есть frequency map отвечает:

сколько?

А grouping отвечает:

какие элементы относятся к этой группе?

Когда нужен grouping

Grouping нужен, когда задача звучит примерно так:

разложить по категориям
найти группы одинаковых элементов
найти анаграммы
сгруппировать по свойству
объединить элементы с одинаковым ключом
собрать элементы по userId / categoryId / parentId

Примеры:

Group Anagrams
Group transactions by user
Group files by extension
Group numbers by remainder
Group intervals by start day

Сложность

Если ключ группы считается за O(1), то построение grouping обычно занимает:

Time:  O(n)
Space: O(n)

где n — количество элементов.

Но если ключ вычисляется дороже, это влияет на итоговую сложность. Например, в
задаче Group Anagrams сортировка букв каждого слова длины m стоит
O(m log m), поэтому общий cost зависит не только от количества слов, но и от
длины слов.

Интуитивная формула

seen set:

элемент -> был / не был

frequency map:

элемент -> сколько раз был

grouping:

ключ группы -> какие элементы туда входят

И это важная штука: grouping часто строится на hash map, просто значение там
не число, а список.

То есть:

HashMap<Key, Count>       // frequency map
HashMap<Key, List<Item>>  // grouping

Мини-резюме

Grouping — это алгоритмический приём, где мы берём набор элементов и
раскладываем их по контейнерам на основе общего признака.

Самая частая форма:

Map<Key, List<Value>>

Например:

sorted letters -> list of anagrams
word length -> list of words
user id -> list of orders
category -> list of products

Если совсем коротко по смыслу:

frequency map считает,
seen set помнит,
grouping раскладывает.