Algorithm to determine one-to-one correspondence with an equivalence function

Question

Suppose that I have two sets of items, and a function to check the equivalence of two items (not strict equality so that one item may be equivalent to multiple items in the other set), I want to determine whether there is a one-to-one correspondence such that the equivalence holds for each of the pairs.

Is there any established/optimal solution for this problem?

---

This problem comes originally from determining whether two C union types are compatible, for which the standard requires such correspondence, however things get tricky as union members can be anonymous so the equivalent item for an item can have multiple possibilities. Currently I'm going with a naive approach but I wonder if there is any establish discussion/solution of it.

Answer 1

One solution is to implement a hash function that has two properties:

1. items that are equivalent have the same hash value
2. items that are not equivalent rarely have the same hash value

Note that a perfect hash function would never generate the same hash value for items that are not equivalent.

Once you have a hash function, you can sort the lists by hash value. If your hash is perfect, it's trivial to check for one-to-one correspondence. If the hash function is less than perfect, when you find an n-to-n correspondence, the code will need to fall back to the brute force O(n^2) equivalence check for those n items.

Running time is the sum of the following tasks

• O(N) to generate hash values
• O(NlogN) to sort the list
• M * O(n^2) for brute force checks (if the hash function is not perfect)

So overall running time with a perfect hash function is O(NlogN) compared to a running time of O(N^2) for a brute force comparison.