5

So, to clarify the question:

Set A and Set B every element in set A has a partner in set B you can not sort either set based upon comparing it to members of the same set, ie, each b element of B is indistinguishable from any other b of set B (likewise for A). when Ai is matched with Bi you can tell if Bi > Ai, Bi < Ai or Bi = Ai. design an algorithm with O(nlogn) running time.

The obvious answer with quadratic time is trivial and not helpful -- although it's the best I've come up with yet. The log(n) makes me think that I should be using recursion or a binary tree of some sort, but I'm not sure how could create a binary tree without being able to compare elements from the same set. Also, I'm not sure how to use a recursive call to any greater effect than just running nested for loops. Any tips would be greatly appreciated.

slmyers
  • 767
  • 1
  • 8
  • 21
  • Sort them and use a single loop to go through all elements. If you have a set data structure from the beginning then, you can just take out the iterator and loop through it. – nhahtdh Oct 11 '12 at 05:45
  • So you are saying A's and B's are not comparable to each other, but you can compare each A to each B and need to finds pairs such that `A == B`? – verdesmarald Oct 11 '12 at 05:49
  • This problem is basically identical to the Matching Nuts and Bolts problem as stated by gowaayacct. Thank you for the attention though. – slmyers Oct 11 '12 at 05:58

1 Answers1

9

You haven't stated it very clearly, but your question looks suspiciously like the Matching Nuts and Bolts problem.

The idea there is to pick a random nut a, find the matching bolt b. Partition the bolts using nut a, and partition the nuts using Bolt b, and then recurse, like quicksort does.

(Of course, we are talking about the average case being nlogn, rather than the worst case).

goawayacct
  • 196
  • 1
  • 1
    Thank you so much, this was very helpful. I'll try to be more clear in the future, and I would vote you up if i had the reputation. – slmyers Oct 11 '12 at 05:56