[Solved]: sock matching algorithm

Problem Detail: 

There are $n$ pairs of socks, all different. They all went out of the dryer, so there are now $2n$ socks scattered around. Given two socks, the only operation I can do is to decide whether they are identical (- belong to the same pair) or different (- belong to different pairs). What is the best way to sort the socks in matching pairs?

The obvious algorithm is: grab a sock, scan the pile for its matching sock, and put that pair aside. This algorithm requires time $O(n^2)$.

I Found a related question, On the complexity of sock-matching from about 10 years ago, which also describes an $O(n^2)$ algorithm.

If each sock has a numeric ID, or another ordinal property, such as: wavelength of color, then the entire set of socks can be sorted by that ordinal property in time $O(n log n)$, and then the pairs can just be collected with an $O(n)$ scan. But, in this question I assume that there is no order on the socks - we can only tell whether two socks are identical or different.

In a similar question in StackOverflow (How to pair socks from a pile efficiently?), the accepted answer suggests to use a hash, but again, this assumes that each sock can be represented by a set of properties such as color, pattern, etc., so that each property can be handled separately. In this question I assume that the properties of the socks are only accessible via a function that tells whether two socks are identical or different.

There is a paper named Sock sorting, which initially seems related, but actually it deals with another problem, where two socks might seem identical although they are different (this probably makes the problem more difficult).

So, my question is: assuming we only have a binary "identical/different" relation on the socks, can we match the socks faster than $O(n^2)$?

Asked By : Erel Segal-Halevi

Answered By : Ron Teller

A comparison with a result "different" doesn't add information regarding any other sock in the pile (If sock B didn't match A, and Sock C didn't match A, the chance of B and C to be a match is still the same as with any other sock). therefor no sorting or organization can be made, rather then knowing for each sock which socks don't match it based on this comparison. this leads back to the naive algorithm, which is $O(n^2)$.

Pretty disappointing...

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16133