algorithmsortinglanguage-agnosticmatching# How can I pair socks from a pile efficiently?

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^{2}/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 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 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?

Solution

Sorting solutions have been proposed, but **sorting is a little too much**: We don't need order; **we just need equality groups**.

So **hashing** would be enough (and faster).

- For each color of socks,
**form a pile**. Iterate over all socks in your input basket**and distribute them onto the color piles**. - Iterate over each pile and
**distribute it by some other metric**(e.g. pattern) into the second set of piles **Recursively apply this scheme**until you have distributed all socks onto**very small piles that you can visually process immediately**

This kind of recursive hash partitioning is actually being done by SQL Server when it needs to hash join or hash aggregate over huge data sets. It distributes its build input stream into many partitions which are independent. This scheme scales to arbitrary amounts of data and multiple CPUs linearly.

You don't need recursive partitioning if you can find a distribution key (hash key) that **provides enough buckets** that each bucket is small enough to be processed very quickly. Unfortunately, I don't think socks have such a property.

If each sock had an integer called "PairID" one could easily distribute them into 10 buckets according to `PairID % 10`

(the last digit).

The best real-world partitioning I can think of is creating a **rectangle of piles**: one dimension is color, the other is the pattern. Why a rectangle? Because we need O(1) random-access to piles. (A 3D cuboid would also work, but that is not very practical.)

Update:

What about **parallelism**? Can multiple humans match the socks faster?

- The simplest parallelization strategy is to have multiple workers take from the input basket and put the socks onto the piles. This only scales up so much - imagine 100 people fighting over 10 piles.
**The synchronization costs**(manifesting themselves as hand-collisions and human communication)**destroy efficiency and speed-up**(see the Universal Scalability Law!). Is this prone to**deadlocks**? No, because each worker only needs to access one pile at a time. With just one "lock" there cannot be a deadlock.**Livelocks**might be possible depending on how the humans coordinate access to piles. They might just use random backoff like network cards do that on a physical level to determine what card can exclusively access the network wire. If it works for NICs, it should work for humans as well. - It scales nearly indefinitely if
**each worker has its own set of piles**. Workers can then take big chunks of socks from the input basket (very little contention as they are doing it rarely) and they do not need to synchronise when distributing the socks at all (because they have thread-local piles). At the end, all workers need to union their pile-sets. I believe that can be done in O(log (worker count * piles per worker)) if the workers form an**aggregation tree**.

What about the element distinctness problem? As the article states, the element distinctness problem can be solved in `O(N)`

. This is the same for the socks problem (also `O(N)`

, if you need only one distribution step (I proposed multiple steps only because humans are bad at calculations - one step is enough if you distribute on `md5(color, length, pattern, ...)`

, i.e. a **perfect hash** of all attributes)).

Clearly, one cannot go faster than `O(N)`

, so we have reached the **optimal lower bound**.

Although the outputs are not exactly the same (in one case, just a boolean. In the other case, the pairs of socks), the asymptotic complexities are the same.

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?