When I do my laundry I tend to make a pile of unmatched socks, putting new socks on the top of the pile and matching off pairs if two of the same sock are near the top of the stack. Since eventually socks will get buried deep in the pile I occasionally dump some of the sock pile back into the laundry pile.
I started to wonder if there was an efficient way to choose when and how I return socks from the sock pile to the laundry pile. So I made up a formalism.
We have two collections of socks, the first one $ L$ represents the laundry pile and the second one $ S$ represents the sock pile. We have perfect knowledge of the contents of both collections. We then have three actions:
-
Move the top sock from $ S$ to $ L$
-
Move a random sock from $ L$ to the top of $ S$
-
Remove the top two socks of $ S$ iff they match. (Make a pairing)
Each sock has exactly one match and at the beginning of execution all the socks are in $ L$ . Our goal is to empty both $ L$ and $ S$ so that all of the socks have been matched off in as little time as possible. I want to measure the efficiency of an algorithm as expected number of performed operations, as a function of the number $ n$ of socks.
What is the most efficient algorithm for this task? What is its asymptotic expected number of operations?
My Algorithm
Here’s the best algorithm I was able to come up with.
In the following, it should go without saying that if you ever encounter a pair on the top of $ L$ you should remove it.
We start with phase one. In phase one we will count the number of complete pairs in $ L$ if there are any pairs in $ L$ we will move an sock from $ L$ to $ S$ , if there are none we will move an sock from $ S$ to $ L$ . We repeat this process until there are exactly three socks, two of them constituting a pair, in $ L$ , then we begin phase two.
In phase two we move one sock from $ L$ to $ S$ if it is not in the pair, we move the last two socks of $ L$ to $ S$ creating a pair, if it is in the pair we have two socks left in $ L$ one that matches the top and one that does not. We keep moving socks from $ L$ to $ S$ moving them back if we do not create a pair. Once we have created a pair we move back to phase one.
The idea for this question is similar to this question, however the actual models for sock matching are radically different.
