Хеширование множеств (с точностью до перестановки)

Материал из Algocode wiki
Версия от 19:43, 4 февраля 2020; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

Хотим научиться сравнивать множества чисел/строк на равенство с точностью до перестановки. Например, $\{1, 2, 3\} = \{2, 1, 3\} \\ \{"lal", "abc"\} = \{"abc", "lal"\} \\ \{4, 5\} \neq \{5, 6\} \\ \{"lal", "abc"\} \neq \{"abc", "all"\}$ .

При этом мы знаем, что количество различных значений, которые могут принимать ключи(объекты, которые лежат в множествах) невелико.

Решение

Сопоставим каждому ключу различные случайные числа (будем называть их хешом ключа) от $0$ до некоторого $M$ (в целом, можно и по модулю $MAX\_LONGLONG$ ), а хешом множества будет считать сумму хешей всех входящих в него ключей. Тогда, очевидно, хеши равных (с точностью до перестановки) множеств будут одинаковые из-за коммутативности сложения, а вероятность коллизий при таком подходе в условиях олимпиад можно считать пренебрежимо малой.



Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex