How to pair socks from a pile efficiently?(stackoverflow.com)
stackoverflow.com
How to pair socks from a pile efficiently?
http://stackoverflow.com/questions/14415881/how-to-pair-socks-from-a-pile-efficiently
15 comments
I own ten identical pairs of black socks. Any sock can be paired with any other. I use a rotation system so they all wear out (approximately) evenly. Every 18 months or so I throw them all out and buy a new set. This reduces the amount of thinking required during laundry and getting ready each morning, which makes me happy.
Same here. 18 pair of initially white socks. After that I just pick one at random and then one that reasonably matches the shade of grey, pink, or blue that it has acquired on its strange and marvelous journey through laundry land.
When most of them have at least one hole I recycle them and start over.
When most of them have at least one hole I recycle them and start over.
Well, I use the opposite strategy. I have 15+ (never counted) pairs of non-identical socks, but they're all very colourful. I prefer stripes, but I will consider other patterns. So, when I sort them out, one look at the laundry basket, it's so obvious which sock pairs with which, that no thinking or inspecting is required.
For reference, these are good socks in my book: http://www.happysocks.com/uk/combed-cotton-polka-stripe-14.h...
The advantage of having such socks is that, since I normally only wear black, it make me seem slightly less boring. The disadvantage is that it's hard to find really worthwhile socks. The secrets of the trade are:
1. Always be alert. If you pass by a sock shop, go in. I once did it on a first date.
2. If you see socks you like, buy them. Don't say "I'll come back later" or "I'll find them online". You'll soon realise it's a buy-now-or-get-heartbroken affair.
3.the Internet is your friend. Compile a list of brands who are more likely to produce good socks and online shops who sell them.
3.5 Pro tip: Swedish brands are very colourful-sock friendly.
4. Visit those online shops regularly to see if they have anything worth buying.
5. You can never have enough socks, so if you see qualifying socks, buy them. You can always store them and use them at a later date.
6. Never buy more than one pair of the same design. The only exception is if there is a pair you see you exceptionally like, in which case you can buy two pairs, but store one pair to when the first pair is too worn out to wear.
Edit: formatting.
Edit 2: this obviously also solves the problem of having to throw good socks out as their general population get worn out.
For reference, these are good socks in my book: http://www.happysocks.com/uk/combed-cotton-polka-stripe-14.h...
The advantage of having such socks is that, since I normally only wear black, it make me seem slightly less boring. The disadvantage is that it's hard to find really worthwhile socks. The secrets of the trade are:
1. Always be alert. If you pass by a sock shop, go in. I once did it on a first date.
2. If you see socks you like, buy them. Don't say "I'll come back later" or "I'll find them online". You'll soon realise it's a buy-now-or-get-heartbroken affair.
3.the Internet is your friend. Compile a list of brands who are more likely to produce good socks and online shops who sell them.
3.5 Pro tip: Swedish brands are very colourful-sock friendly.
4. Visit those online shops regularly to see if they have anything worth buying.
5. You can never have enough socks, so if you see qualifying socks, buy them. You can always store them and use them at a later date.
6. Never buy more than one pair of the same design. The only exception is if there is a pair you see you exceptionally like, in which case you can buy two pairs, but store one pair to when the first pair is too worn out to wear.
Edit: formatting.
Edit 2: this obviously also solves the problem of having to throw good socks out as their general population get worn out.
Same here, except that I have a set of black and a set of white (I mostly wear white), which are kept in separate drawers.
I don't have a formal rotation system, though. Just drawing at random from the drawer seems to produce approximately equal wear.
I don't have a formal rotation system, though. Just drawing at random from the drawer seems to produce approximately equal wear.
This, but dark brown instead, as more universal color. Buy in bulk 20 pairs (I use http://www.blacksocks.com/ since they seem to keep same model in stock, other producers seem to rename their socks - never can find the same socks later). Once they show signs of too much wear, order new batch and throw all old ones away.
Of course I also own few other colors for special occasions and sport socks, they go to separate drawer.
Of course I also own few other colors for special occasions and sport socks, they go to separate drawer.
The 10 identical pairs of black socks doesn't really work for business casual and up unless all your dress pants happen to be black as well.
To be honest I'd think nothing of wearing back socks and grey/khaki pants.
I think you're fine if you're wearing black shoes, no?
I'd agree khaki pants with brown shoes would be weird with black socks
I'd agree khaki pants with brown shoes would be weird with black socks
Traditional fashion wisdom is that socks should match pants. If you match your pants to your shoes, it makes it look like you're wearing high-tops. It draws attention away from your shoes when you want to be drawing attention toward your shoes.
If you don't care about fashion, it doesn't matter, though
If you don't care about fashion, it doesn't matter, though
I go for grey socks. You can wear grey with basically any pair of dress pants. With non-dress pants, I just don't wear socks.
I had a similar problem at a previous job. I was given bundles of orders that needed to be sorted and filed. Being the old days, these orders were sheets of paper with numbers on them, and "filed" meant in filing cabinets.
I fairly quickly moved to an algorithm that I would later learn was MSB radix-sort. Basically, I made one iteration and divided them into buckets with the same value in the "hundreds" column, and then recurse into each pile and repeat for the "tens" column, then a quick sort for the final 10 orders.
As a concrete example, lets say I had 150 orders with order numbers between 7200 and 7499. Organize into piles containing the 7200s, the 7300s and the 7400s. Then take the 7200s, and split it into piles for 7200s, 7210s, 7220s, etc.
In sorting algorithms, it common to use insertion sort for the final step (actually, people often use any O(N^2) sort, but really should only ever use insertion sort because its the most efficient O(N^2) sort in terms of instruction count, cache locality, and branch mispredictions).
I fairly quickly moved to an algorithm that I would later learn was MSB radix-sort. Basically, I made one iteration and divided them into buckets with the same value in the "hundreds" column, and then recurse into each pile and repeat for the "tens" column, then a quick sort for the final 10 orders.
As a concrete example, lets say I had 150 orders with order numbers between 7200 and 7499. Organize into piles containing the 7200s, the 7300s and the 7400s. Then take the 7200s, and split it into piles for 7200s, 7210s, 7220s, etc.
In sorting algorithms, it common to use insertion sort for the final step (actually, people often use any O(N^2) sort, but really should only ever use insertion sort because its the most efficient O(N^2) sort in terms of instruction count, cache locality, and branch mispredictions).
I've been thinking about this algorithm. If you had millions of items, then wouldn't the process of dividing into buckets, and then sorting these buckets which are massive take a long time? Unless of course you recursively sort each bucket into sub-buckets...
It's typical to recurse until you're down to small enough sets to easily sort using some other algorithm (usually insertion sort on groups < 10 elements.)
With radixsort, you don't even need to. By the time you get to the deepest bucket, all the entries have an identical prefix and unique suffix. So they can all be sorted in O(N).
You could construct situations where it would be faster to switch to insertion sort (maybe radix of 2, stop 3 recursions from the end), but in practice you'd pick a radix better (with a radix of 8, you could do the entire thing in 4 recursions and the final recursion over 64 items is faster than insertion sort of 64 items, probably).
Note that you'd generally use LSB radixsort over MSB radixsort, so you'd have a set number of passes over the array, and no recursion.
You could construct situations where it would be faster to switch to insertion sort (maybe radix of 2, stop 3 recursions from the end), but in practice you'd pick a radix better (with a radix of 8, you could do the entire thing in 4 recursions and the final recursion over 64 items is faster than insertion sort of 64 items, probably).
Note that you'd generally use LSB radixsort over MSB radixsort, so you'd have a set number of passes over the array, and no recursion.
You recursively sort each bucket into subbuckets, and there is a known recursion limit (3 in this case).
Here's code for an LSB radix sort, which doesn't recurse, but is the same idea: https://github.com/pbiggar/sorting-branches-caching/blob/mas...
Here's code for an LSB radix sort, which doesn't recurse, but is the same idea: https://github.com/pbiggar/sorting-branches-caching/blob/mas...
Just a few thoughts on the solution...
If you find a way to not jumble the socks as you fish around, you will be able to remember their locations. (up to a certain number)
The human brain is very parallel in it's image recognition, if your socks look different enough just placing your gaze in the general vicinity will lead to a match.
As you find pairs, the stack size gets smaller. (making the above two effects increase their strength)
Some socks will have multiple valid 'buddy' socks. (think a pack of identical socks... each sock will match any other)
So, version one: - Spread your socks out all over the floor/table - Pick up a sock that appears to be the most common. (you can optimize this later by memorizing the 5 or so types of socks you have the most of) - Find a matching sock, return to step two.
Hopefully, this will allow the decreasing pile size to counteract the depletion of easily-matched socks, keeping the whole thing under your brain's limits for parallel sock matching.
(I'm posting this here because I'd like some peer review before I make my answer final.)
If you find a way to not jumble the socks as you fish around, you will be able to remember their locations. (up to a certain number)
The human brain is very parallel in it's image recognition, if your socks look different enough just placing your gaze in the general vicinity will lead to a match.
As you find pairs, the stack size gets smaller. (making the above two effects increase their strength)
Some socks will have multiple valid 'buddy' socks. (think a pack of identical socks... each sock will match any other)
So, version one: - Spread your socks out all over the floor/table - Pick up a sock that appears to be the most common. (you can optimize this later by memorizing the 5 or so types of socks you have the most of) - Find a matching sock, return to step two.
Hopefully, this will allow the decreasing pile size to counteract the depletion of easily-matched socks, keeping the whole thing under your brain's limits for parallel sock matching.
(I'm posting this here because I'd like some peer review before I make my answer final.)
This is what I do: lay them out and pair them as the layout continues. O(n) to pair n socks, but that's cheating a bit because you can see them all at a glance. Particularly works well with my daughter's socks, the little ones are really hard to keep track of.
I have an O(1) solution that is fairly reliable for matching a single pair. Pick out a sock from the drawer. Then go find your kids; they ran off with the matching one when you weren't looking (requires that you live with at least one young child).
I have an O(1) solution that is fairly reliable for matching a single pair. Pick out a sock from the drawer. Then go find your kids; they ran off with the matching one when you weren't looking (requires that you live with at least one young child).
My answer is not fully algorithmic yet "efficient" when I do it :
step 1) discard all your existing socks
step 2) go to walmart and buy them by packets of 10 - n packet of white and m packets of black. No need for other colors in everyday's life.
Yet times to times I have to do this again (lost socks, damaged socks etc.) and I hate to discard perfectly good socks too often (and I wished they kept selling the same socks reference!) so I recently took a different approach.
Consider than if you draw only 1 sock for the 2n stack of socks, your odds of finding the matching sock in a naive search is quite low.
Pick up 5 of them at random (usually humans are good are remembering between 4 and 7 different elements in the working memory - a bit like the human equivalent of a RPN stack - 5 is a safe default) and memorize their shape or their length.
Pick up one from the stack of 2n-5.
Now look for a match (visual pattern matching - humans are good at that with a small stack) inside the 5 you drew, if you don't find one, then add that to your 5 and keep randomly picking socks from the stack and compare to your 5+1 socks for a match (it will reduce your performances but raise your odds)
Much faster. Feel free to write down the formula (it's late, I'm getting sleepy) to calculate how much samples you have to draw for a 50% odds of a match. IIRC it's an hypergeometric law.
I do that every morning and rarely need more than 3 draws. Now you can estimate the size of my stack of stocks :-)
BTW I found that the transaction costs of sorting all the socks every time I needed a pair were far less than doing it once and binding the socks - because then you don't have to bind the socks, and there's also a diminishing marginal return (ie you keep looking for that 2 or 3 socks that when somewhere in the laundry and that you need to finish matching your socks and you lose time on that)
step 1) discard all your existing socks
step 2) go to walmart and buy them by packets of 10 - n packet of white and m packets of black. No need for other colors in everyday's life.
Yet times to times I have to do this again (lost socks, damaged socks etc.) and I hate to discard perfectly good socks too often (and I wished they kept selling the same socks reference!) so I recently took a different approach.
Consider than if you draw only 1 sock for the 2n stack of socks, your odds of finding the matching sock in a naive search is quite low.
Pick up 5 of them at random (usually humans are good are remembering between 4 and 7 different elements in the working memory - a bit like the human equivalent of a RPN stack - 5 is a safe default) and memorize their shape or their length.
Pick up one from the stack of 2n-5.
Now look for a match (visual pattern matching - humans are good at that with a small stack) inside the 5 you drew, if you don't find one, then add that to your 5 and keep randomly picking socks from the stack and compare to your 5+1 socks for a match (it will reduce your performances but raise your odds)
Much faster. Feel free to write down the formula (it's late, I'm getting sleepy) to calculate how much samples you have to draw for a 50% odds of a match. IIRC it's an hypergeometric law.
I do that every morning and rarely need more than 3 draws. Now you can estimate the size of my stack of stocks :-)
BTW I found that the transaction costs of sorting all the socks every time I needed a pair were far less than doing it once and binding the socks - because then you don't have to bind the socks, and there's also a diminishing marginal return (ie you keep looking for that 2 or 3 socks that when somewhere in the laundry and that you need to finish matching your socks and you lose time on that)
I "hash" them into "buckets" of like socks and then pair from each bucket. Remaining unpaired socks either went through the wash absent their mate, or witnessed its gory demise at the hands of the washing machine monster.
This to me makes the most sense as there are a couple of characteristics to "hash" a sock on.
I solve the problem by keeping the socks paired using sock holders while they are washed. Also by using different colors for each family member, you solve the distribution problem.
http://www.sockpro.com/
http://www.sockpro.com/
It's bit silly (obviously) to talk about this in terms of sorting algorithms, because the scan operation is so lightweight. I sort my socks by pulling one out of the pile and visually scanning all the single socks i have laid out separately on the floor. If there's a match, i pair them and put the pair in the drawer. If there is no match, I lay the sock on the floor by itself. In computational terms, this is incredibly inefficient, but in practical terms the visual scan where i iterate over all the single socks laid out on the floor is quicker than the pick-a-sock-from-the-pile operation, so typical algorithm analysis is really quite useless.
Yeah, people are using sequential algorithms when vision is parallel processing.
When you get the socks, attach a pair identifier to each sock in the pair. The ids start at 0 and increment by one for each new pair.
When a sock is lost, discard it's peer. When the pair is replaced, reuse the id. This keeps the ids dense.
After doing the laundry, you can place each sock based on its id, and match up everything in O(n).
Washing them paired up (one rolled inside the other) is even better, O(n), where n is the number of pairs, not the number of socks. But I don't think the socks get really clean.
When a sock is lost, discard it's peer. When the pair is replaced, reuse the id. This keeps the ids dense.
After doing the laundry, you can place each sock based on its id, and match up everything in O(n).
Washing them paired up (one rolled inside the other) is even better, O(n), where n is the number of pairs, not the number of socks. But I don't think the socks get really clean.
Well, the socks are paird when you take them off, so it makes sense to keep entropy at bay rather than fighting the same dreary battles over and over. Use these http://deseng.ryerson.ca/xiki/Learning/Main:Sock_clips or some equivalent, I'm sure there are plenty of options :-)
Outsource it - the maid / laundry does that stuff.
RFID tags and, uh, a robot thing.
RFID tags and, uh, a robot thing.
Avoid the problem by not having to pair them at all.
This can be done two ways:
Either have only one color.
The other option is to make it your thing to have odd pairs. Works better the more different from each other they are.
This can be done two ways:
Either have only one color.
The other option is to make it your thing to have odd pairs. Works better the more different from each other they are.
Buy only Plus+ socks.
http://www.blacksocks.com/en-us/smartersocks_simplyexplained...
http://www.blacksocks.com/en-us/smartersocks_simplyexplained...
1>Throw them out.
2>Buy identical socks.
3>Stop worrying about it.
2>Buy identical socks.
3>Stop worrying about it.
[deleted]