Suppose you have two lists, A
and B
, each with length n. The elements of A cannot be compared with other elements of A
--there is no order relation among them--and likewise for B
. However, elements of A
can be compared with elements of B
. So for instance, suppose we have a function compareTo(a,b)
where a
is an element of A
and b
is an element of B
. If a
is less than b
it returns -1, if they're equivalent it returns 0, and if a
is greater it returns 1.
Further suppose that a perfect matching exists between the elements of A
and B
, in the sense that for every element of A
there is precisely one element of B
such that compareTo(a,b)
evaluates to 0. And vice versa (for each b
there is precisely one a
such that they're equivalent).
How do we write an efficient algorithm to find the perfect matching?
My attempts: Well, there's the naive algorithm which takes an element of A
and finds its corresponding element of B
, repeating until all matchings have been found. This runs in O(n^2) so we want to beat this.
It sounds kind of like Gale-Shapley but an input to that algorithm is a preference list. In this setting we have ties, where preference lists don't. And even generating something like a preference list would take n^2 time. Since it is fundamental to Gale-Shapley that members of one set propose to their highest preferences of the other, this doesn't seem applicable to the given problem.
We could try to use an element of A
to partition the set B
and try to divide-and-conquer. But you would only have divided B
and wouldn't know which elements of A
to give to the recursive call. You could then try to use B
to partition A
. To describe this more, let's give a specific example. Suppose A = [a1,a2,a3,a4]
and B = [b4,b1,b3,b2]
and suppose that ai < bj
if i < j
, and likewise for =
and >
. We could arbitrarily select a1
and then use it to partition B
into the elements that come out greater in the comparison, [b4,b3,b2]
and the elements that come out smaller []
. Since along the we way we found that a1
matched b1
we make that assignment and eliminate them from the rest of the algorithm. Now that we know a1
was quivalent to b1
we can use b1
to partition A
into []
and [a2,a3,a4]
. We recursively call the algorithm on the smaller sets [], []
which satisfies the conditions: they have the same length and have perfect matching. And recursively call the algorithm on the larger sets [a2,a3,a4], [b4,b3,b2]
which also have the same length and have a perfect matching.
I think this algorithm is correct, but in the worst case it doesn't beat the worst-case runtime of the naive algorithm. So I don't think I'm on the right track here.