How can I pair socks from a pile efficiently?

4211

Yesterday I was pairing the socks from the clean laundry and figured out the way I was doing it is not very efficient. I was doing a naive search — picking one sock and "iterating" the pile in order to find its pair. This requires iterating over n/2 * n/4 = n²/8 socks on average.

As a computer scientist I was thinking what I could do? Sorting (according to size/color/...) of course came to mind to achieve an O(NlogN) solution.

Hashing or other not-in-place solutions are not an option, because I am not able to duplicate my socks (though it could be nice if I could).

So, the question is basically:

Given a pile of n pairs of socks, containing 2n elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space? (I believe I can remember that amount of info if needed.)

I am seeking an answer that addresses the following aspects:

A general theoretical solution for a huge number of socks.
The actual number of socks is not that large, I don't believe my spouse and I have more than 30 pairs. (And it is fairly easy to distinguish between my socks and hers; can this be used as well?)
Is it equivalent to the element distinctness problem?

Edit Report

1 Answer

114

What I do is that I pick up the first sock and put it down (say, on the edge of the laundry bowl). Then I pick up another sock and check to see if it's the same as the first sock. If it is, I remove them both. If it's not, I put it down next to the first sock. Then I pick up the third sock and compare that to the first two (if they're still there). Etc.

~~This approach can be fairly easily be implemented in an array, assuming that "removing" socks is an option.~~ Actually, you don't even need to "remove" socks. If you don't need sorting of the socks (see below), then you can just move them around and end up with an array that has all the socks arranged in pairs in the array.

Assuming that the only operation for socks is to compare for equality, this algorithm is basically still an n² algorithm, though I don't know about the average case (never learned to calculate that).

Sorting, of course improves efficiency, especially in real life where you can easily "insert" a sock between two other socks. In computing the same could be achieved by a tree, but that's extra space. And, of course, we're back at NlogN (or a bit more, if there are several socks that are the same by sorting criteria, but not from the same pair).

Other than that, I cannot think of anything, but this method does seem to be pretty efficient in real life. :)

answered 2013-01-19T15:49:31.150

How can I pair socks from a pile efficiently?

1 Answer

Your Answer