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.

bumped to the homepage by Community 2 days ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

  • 1
    Possibly related. – Raphael May 15 '17 at 5:11
  • I think this question is too broad. There are infinitely many algorithms for any problem; which are those you are interested in? – Raphael May 15 '17 at 5:13
  • "I am interested in the algorithm with the best average time complexity. " -- Expected time in which input model? "Best" w.r.t. Landau notation or with constant factors or ... ? "What do you mean by "There are infinitely many algorithms for any problem"?" -- I don't see what's ambiguous about this statement. (It's a well-known result in recursion theory: every Turing-complete model has infinitely many machines/programs/... for every computable problem.) – Raphael May 15 '17 at 5:19
  • 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
  • 1
    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

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)$. – W W 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++)
    {
        Laundry.Add(i);
        Laundry.Add(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)
        {
            Unmatched.Add(Sock);
        }
        else
        {
            if (Sock == LastUnmatched)
            {
                Matched.Add(Sock);
                Unmatched.Remove(Sock);
            }
            else
                Unmatched.Add(Sock);
        }
        LastUnmatched = Sock;
    }
    Debug.WriteLine(count);
}
  • "I see no benefit to dumping the UN back periodically", "move all but 1 sock from UN from RS". These two statements seem to directly contradict each other. – W W Jun 14 '17 at 20:21
  • @EpsilonNeighborhoodWatch That means until RS is empty - you have to. – paparazzo Jun 14 '17 at 20:23
  • In step 2 you also say "remove 1 sock from UN and place on UN" I assume this is a typo but I do not know what your intention here was. – W W Jun 14 '17 at 20:25
  • @EpsilonNeighborhoodWatch Corrected – paparazzo Jun 14 '17 at 20:28
  • 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. – W W Jun 14 '17 at 20:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.