You Must Be From Away

From Jason Kottke’s kottke.org

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 into 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 will appreciate 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 me and my spouse have more than 30 pairs. (And it is fairly easy to distinguish between my socks and hers, can this be utilized as well?)
• Is it equivalent to the element distinctness problem?

One option:

Suppose that you know that your 2n socks are arranged this way:

p₁ p₂ p₃ … p_n p_f(1) p_f(2) … p_f(n)

where f is an unknown permutation of the set {1,2,…,n}. Knowing this cannot make the problem harder. There are n! possible outputs (matchings between first and second half), which means you need log(n!) = Omega(n log n) comparisons. This is obtainable by sorting.

Since you are interested in connections to element distinctness problem: proving the Omega(n log n) bound for element distinctness is harder, because the output is binary yes/no. Here, the output has to be a matching and the number of possible outputs suffices to get a decent bound. However, there’s a variant connected to element distinctness. Suppose you are given 2n socks and wonder if they can be uniquely paired. You can get a reduction from ED by sending (a₁, a₂, …, a_n) to (a₁, a₁, a₂, a₂, …, a_n, a_n). (Parenthetically, the proof of hardness of ED is very interesting, via topology.)

I think that there should be an Omega(n²) bound for the original problem if you allow equality tests only. My intuition is: Consider a graph where you add an edge after a test, and argue that if the graph is not dense the output is not uniquely determined.

Another option

List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchSock != null)
  {
    PairedSocks.Add(new PairOfSocks(MatchSock, NewSock));
    UnmatchedSocks.remove(MatchedSock);
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

The right answer

1) Throw all your socks out.

2) Go to Uniqlo and buy 15 identical pairs of black socks.

3) When you want to wear socks, pick any two out of the drawer.

4) When you notice your socks are wearing out, goto step 1.