Хеширование множеств (с точностью до перестановки): различия между версиями
Строка 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"\}$ . |
При этом мы знаем, что количество различных значений, которые могут принимать ключи(объекты, которые лежат в множествах) невелико. | При этом мы знаем, что количество различных значений, которые могут принимать ключи(объекты, которые лежат в множествах) невелико. |
Версия 13:54, 24 января 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$), а хешом множества будет считать сумму хешей всех входящих в него ключей. Тогда, очевидно, хеши равных (с точностью до перестановки) множеств будут одинаковые из-за коммутативности сложения, а вероятность коллизий при таком подходе в условиях олимпиад можно считать пренебрежимо малой.