Хеширование множеств (с точностью до перестановки): различия между версиями
(Новая страница: «== Задача == Хотим научиться сравнивать множества чисел/строк на равенство с точностью до...») |
м |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
== Задача == | == Задача == | ||
− | Хотим научиться сравнивать множества чисел/строк на равенство с точностью до перестановки. Например, $\{1, 2, 3\} = \{2, 1, 3\} | + | Хотим научиться сравнивать множества чисел/строк на равенство с точностью до перестановки. Например, $\{1, 2, 3\} = \{2, 1, 3\} \\ \{"lal", "abc"\} = \{"abc", "lal"\} \\ \{4, 5\} \neq \{5, 6\} \\ \{"lal", "abc"\} \neq \{"abc", "all"\}$ . |
При этом мы знаем, что количество различных значений, которые могут принимать ключи(объекты, которые лежат в множествах) невелико. | При этом мы знаем, что количество различных значений, которые могут принимать ключи(объекты, которые лежат в множествах) невелико. | ||
Строка 7: | Строка 7: | ||
== Решение == | == Решение == | ||
− | Сопоставим каждому ключу различные случайные числа (будем называть их хешом ключа) от $0$ до некоторого $M$ (в целом, можно и по модулю $ | + | Сопоставим каждому ключу различные случайные числа (будем называть их хешом ключа) от $0$ до некоторого $M$ (в целом, можно и по модулю $MAX\_LONGLONG$ ), а хешом множества будет считать сумму хешей всех входящих в него ключей. Тогда, очевидно, хеши равных (с точностью до перестановки) множеств будут одинаковые из-за коммутативности сложения, а вероятность коллизий при таком подходе в условиях олимпиад можно считать пренебрежимо малой. |
+ | |||
+ | {{Автор|Александр Гришутин|rationalex}} |
Текущая версия на 16:43, 4 февраля 2020
Задача
Хотим научиться сравнивать множества чисел/строк на равенство с точностью до перестановки. Например, $\{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