Алгоритм определения взаимно-однозначного соответствия с функцией эквивалентности

Question

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

Есть ли какое-либо установленное / оптимальное решение для этой проблемы?

---

Эта проблема изначально возникает из-за определения совместимости двух типов объединения C, для которых стандарт требует такого соответствия, однако все становится сложнее, поскольку члены объединения могут быть анонимными, поэтому эквивалентный элемент для элемента может иметь несколько возможностей. В настоящее время я придерживаюсь наивного подхода, но мне интересно, есть ли какое-либо обоснованное обсуждение / решение этого вопроса.

Answer 1

Одним из решений является реализация хеш-функции, которая имеет два свойства:

1. элементы, которые эквивалентны, имеют одинаковое значение хеш
2. элементы, которые не являются эквивалентными, редко имеют одинаковое хеш-значение

Обратите внимание, что совершенная хеш-функция никогда не будет генерировать одинаковое хеш-значение для элементов, которые не эквивалентны.

Если у вас есть хеш-функция, вы можете отсортировать списки по хеш-значению. Если ваш хэш идеален, проверять соответствие "один к одному" тривиально. Если хеш-функция не идеальна, когда вы найдете соответствие n-n-n, коду придется вернуться к проверке эквивалентности грубой силы O(n^2) для этих n Предметы.

Время выполнения - это сумма следующих задач

• O(N) для генерации хеш-значений
• O(NlogN), чтобы отсортировать список
• M * O(n^2) для проверки методом грубой силы (если хеш-функция не идеальна)

Таким образом, общее время работы с идеальной хэш-функцией составляет O(NlogN) по сравнению с временем работы O(N^2) для сравнения методом грубой силы.