# How to Match Socks

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.

• – Raphael May 15 '17 at 5:11
• What you can do to avoid making this too broad is provide objective criteria that enable us to identify a single correct answer (or single best answer). For instance: "I'm interested to see what algorithms come up with": too broad and open-ended; has no criteria for judging. "What is the most efficient algorithm for this task?": focused enough that we can evaluate answers (according to the measure of efficiency you provide). So replacing the former with the latter would address the "too broad" criticism. – D.W. May 15 '17 at 16:59
• OK, I made an edit to implement what I was hinting at. I replaced the "I'm interested to see what algorithms others can come up with" with an explicit question (a question that can have a single right answer). – D.W. May 15 '17 at 17:11
• How is the actual model for sock matching different? Is it not two socks match - true or false. – paparazzo Jun 14 '17 at 19:10
• @Paparazzi I guess that was poor wording on my part, the model for sock matching is the same, the model for what actions you are allowed to take when matching socks is different. – Sriotchilism O'Zaic Jun 14 '17 at 19:13

Suppose there are $n$ socks, of $m$ types. It's easy to pair off all the socks with $O(n^2)$ expected running time. I will show an algorithm that achieves $O(nm)$ expected running time. I don't know whether this is optimal.

# Notation

Let $T$ denote the set of types of the socks, so $m=|T|$. I'll assume two socks can be paired iff they're of the same type. Let $p(t)$ denote the probability that, if you pick a sock uniformly at random from all of the available socks, its type will be $t$.

# Algorithm

Here's the algorithm. Define $t^*$ to be the type of the most common sock (i.e., with maximal $p(\cdot)$ value). Start with an empty stack. Draw a random sock from $L$; if it isn't of type $t^*$, throw it back and repeat until the stack contains a single sock of type $t^*$. Now do that again: draw a random sock from $L$; if it isn't of type $t^*$, throw it back and repeat until the stack contains two socks of type $t^*$. Remove the pair. Now you have $n-2$ socks; recurse.

What's the expected running time of this algorithm? It takes $1/p(t^*)$ draws until you see the first sock of type $t^*$ (multiply by two, to take into account throwing back the ones you didn't want). Then it takes another $1/p(t^*)$ draws to get the second sock of type $t^*$ (again, multiply by two for the same reason). So, it will take about $4/p(t^*)$ draws to find one pair. How large could this be? In other words, how small could $p(t^*)$ be? Well, it's easy to see that $p(t^*) \ge 1/m$. Consequently, after at most $4m$ draws, we have removed one pair. We repeat until we've found all pairs, i.e., $n/2$ times. (At each stage, the number of types can only decrease so the value of $p(t^*)$ can only increase.) So, the total number of operations is at most $4m \times n/2 = O(nm)$.

# Possible direction for improvement

If you wanted to improve further, you could try experimenting with the following idea. Unfortunately, I don't know how to analyze its worst-case running time in terms of $n$ and $m$.

Pick a threshold $q$. Define $T_q = \{t \in T : p(t) \ge q\}$. Now replace the algorithm above with one that repeatedly draws from $L$ and throws back until the stack contains a single sock whose type is in $T_q$; then repeatedly draw and throw back until you find another sock of the same type. Once you find a match, pair them off and recurse.

How long will it take to find the first match? It will take $1/\sum_{t \in T_q} p(t)$ iterations to find the first sock, and (crudely) $\le 1/q$ iterations to find the second stock. More precisely, the total number of iterations will be (after some manipulation)

$${1+|T_q| \over \sum_{t \in T_q} p(t)}$$

You can now find the $q$ that minimizes that value, then apply the strategy above. I don't know whether this leads to any improvement in asymptotic running time, as a function of $n$ and $m$.

• The question, at least as I asked it, has $m$ set to be the same as $n/2$, that is each sock has one unique match. This doesn't make the answer invalid, but it does mean its run time is $O(n^2)$. – Sriotchilism O'Zaic May 15 '17 at 17:45
• @EpsilonNeighborhoodWatch, oh, you are right! My fault -- I missed that part of the question. I guess this is not very useful, then. Sorry about that. The natural question is whether one can do better than $O(n^2)$, and this doesn't help with that. – D.W. May 15 '17 at 20:09

I assume you get to remove the matched socks

I am going to call them
RS for random socks
UN for unmatched
MA for matched
N is total number of socks

I see no benefit to dumping the UN back periodically

As in poker a dealt down card card is still unknown. The next card is still random. You have just as much chance the first two cards pair as the last two.

1. move 1 sock from RS and place on UN
2. remove 1 sock from RS and place on UN
the chance of a match is N - 1 - (size of MA)
if it matches the top sock move the pair to MA
in this case MA is an up or known sock
3. when there are no more socks in RS move all but 1 sock from UN to RS
you don't even need to shuffle as the remaining socks will still be random
4. go to step 2. until there are zero socks in UN

Now what is the order. Assume the first pair is found in (N-1) / 2 and after that every N - 1 - MA.

S = N/2
UN = N
count = 0
while (UN > 0)
{
count++
S++
if (count == UN - 1)
{
UN -= 2
count = 0
}
}


OP this code please test it out
It is slightly different than the algorithm in I don't leave 1 in UN
I am confident it does a minimum number of comparisons and minimum moves
Remove and insert are expensive operations
On your code you need to include the cost of count matches in L
You don't get to spike the pool to increase the chance of a match and not charge for those steps
If you are not picking randomly for the L I think that is cheating

public static void MatchSocks()
{
Random rand = new Random();
List<int> Laundry = new List<int>();
List<int> Matched = new List<int>();
List<int> Unmatched = new List<int>();
int? LastUnmatched = null;
int Sock;
int count = 0;
for (int i = 0; i < 500; i++)
{
}
while (true)
{
count++;
if(Laundry.Count == 0)
{
if (Unmatched.Count == 0)
break;
Laundry = new List<int>(Unmatched);
Unmatched.Clear();
LastUnmatched = null;
}
Sock = Laundry.ElementAt(rand.Next(Laundry.Count));
Laundry.Remove(Sock);
if (LastUnmatched == null)
{
}
else
{
if (Sock == LastUnmatched)
{
Unmatched.Remove(Sock);
}
else

• In addition, if I understand correctly, this algorithm you are suggesting is less efficient than the one provided in the question. When you move everything in UN to RA you are essentially minimizing the chance that you will get a pair ($1/(N-1)$ is the worst chance you can ever have of obtaining a match). If you remove until a pair is in RA you can expect approximately $n$ more steps until a match where $n$ is the number removed (for small $n$ the chance is larger but the chance asymptotically approaches $n$). That $n$ will increase only logarithmically as $N$ increases. – Sriotchilism O'Zaic Jun 14 '17 at 20:33