Timeline for How can I pair socks from a pile efficiently?

Current License: CC BY-SA 4.0

130 events
when toggle format what by license comment
Sep 1 at 21:17 comment added gurkensaas Maybe you need to sort the array of socks first to achieve such speeds.
May 6 at 16:44 comment added val is still with Monica @Mxyk I'm a little scared to ask, why do your children die when they are done soting socks? This seems suboptimal (and cruel).
Apr 28 at 6:08 comment added David Peer great Question!
Apr 13 at 6:35 answer AlDante timeline score: 4
Apr 23 '20 at 19:19 history edited Peter Mortensen CC BY-SA 4.0
Fixed the question formation - missing auxiliary (or helping) verb - see e.g. <https://www.youtube.com/watch?v=t4yWEt0OSpg&t=1m49s> (see also <https://www.youtube.com/watch?v=kS5NfSzXfrI> (QUASM)) - the alternative is to leave out the question mark (the "How to ...=" is too illiterate).
Jan 9 '20 at 12:40 comment added Chris Melville Step 1) Throw away all your current socks. Step 2: buy 15 pairs of identical black socks for yourself, and 15 pairs of identical white socks for your wife. Step 3) The algorithm reads: "Black socks are yours, and white socks are your wife's"!
May 15 '19 at 10:00 review Close votes
May 19 '19 at 0:00
May 10 '19 at 18:15 review Close votes
May 14 '19 at 0:00
Apr 30 '19 at 0:35 review Close votes
May 4 '19 at 0:00
Oct 26 '18 at 11:05 review Close votes
Oct 30 '18 at 0:00
Jan 22 '18 at 22:03 comment added Cee McSharpface your assumption about matching pairs is soooo removed from reality. even with two parallel.task(child).waitpid.all the performance gain the accepted answer promises is outweighed by the exponential decline of the number of matching specimen in the pile over time.
Nov 16 '17 at 18:08 review Close votes
Nov 20 '17 at 0:07
Sep 29 '17 at 13:23 comment added Chris Phillips For socks, I think using a bucket sort would be the most efficient method. have your pile in one spot and your buckets in another. pull a sock, put it in a new pile of socks that match that sock. as long as you have enough table space, you can sort your socks in O(n) time, which is the lower limit, if you're doing this yourself. adding extra workers allows you to push towards O(log n)
Aug 17 '17 at 18:18 answer JMan Mousey timeline score: 3
Feb 16 '17 at 2:53 answer Laszlo timeline score: 5
Jul 22 '16 at 15:52 history edited Steve Chambers CC BY-SA 3.0
Made title into a question in a consistent format with other top questions
Jun 21 '16 at 12:56 review Suggested edits
Jun 21 '16 at 15:27
Oct 19 '15 at 20:47 answer Nikolay Dyankov timeline score: 32
Jun 12 '15 at 3:11 history edited blockhead CC BY-SA 3.0
Grammar fix
May 28 '15 at 16:47 history edited Bergi
edited tags
May 27 '15 at 19:13 answer wrzasa timeline score: 9
May 4 '15 at 21:36 history wiki removed Taryn
Feb 24 '15 at 5:07 comment added woot How do you account for the sock without its pair that the dryer monster ate?
Feb 2 '15 at 18:50 history edited Peter Mortensen CC BY-SA 3.0
Copy edited. Ref. <http://en.wikipedia.org/wiki/User:Tony1/How_to_improve_your_writing#Misplaced_formality>.
Nov 19 '14 at 19:29 comment added Persixty I have also solved the practical problem in O(1) time, by only buying black socks in packs of 50 pairs. It's interesting how many Stack Overflow posters have found the same solution!
Oct 31 '14 at 13:25 history edited ProgramFOX CC BY-SA 3.0
Improved title: http://meta.stackexchange.com/questions/10647/how-do-i-write-a-good-title
Sep 21 '14 at 8:49 answer SF. timeline score: 9
Jul 7 '14 at 20:25 comment added cnsumner The other problem that everyone else seemed to overlook is the problem of finding a sock's exact match (not just same color and size). I always keep socks with their respective partners so that they wear the same, so if I don't find the exact sock I have always worn with the other sock, they will feel different (unacceptable to my OCD programmer mind) even though they originated from the exact same package.
May 25 '14 at 9:46 answer Khaled.K timeline score: 3
May 7 '14 at 15:38 comment added amit @Geek You need to pair n/2 socks (this is where n/2 came from). by taking one sock, and finding its match. On average, you need to go through half of the left socks. At the first iteration this number is n/2, at second, (n/2)/2, ... the average of n/2,(n-2)/2,(n-4)/2,...,2/2 is n/4.
May 7 '14 at 15:02 comment added Geek @amit you wrote using your naive technique you were doing This requires iterating over n/2 * n/4 = n2/8 socks on average.. What is the reasoning for this? How are the terms n/2 and n/4 appearing?
May 2 '14 at 6:12 comment added Keith The optimum solution to the sock pairing problem is to put them into the laundry as a pair. This reduces sort time to zero and resolves the single sock problem.
Apr 30 '14 at 22:33 comment added Vasil Dininski I am sure someone has already posted this, but you are inferring from the incorrect assumption that there is a pair for each sock. I mean - come on, do you really think that each sock that you are laundering has a matching one...
Apr 30 '14 at 9:18 answer Philipp timeline score: 10
Apr 30 '14 at 3:13 comment added user1164937 You can save memory by immediately stuffing the pile from the basket to the drawer instead of spreading them out on a surface (to find matching pairs). Just look for a matching pair from the drawer when you need it.
Apr 3 '14 at 8:38 comment added thang @ApprenticeQueue say you're right, what would the choice function look like? I think that you are (provably) wrong, but to give a hint, have a look at this: en.wikipedia.org/wiki/Axiom_of_countable_choice (a weaker version of AC). To prove that even axiom of countable choice is independent of ZF is difficult and uses forcing.
Apr 2 '14 at 23:21 comment added Apprentice Queue @thang, you don't need to assume the Axiom of Choice if the number of socks is countable.
Mar 25 '14 at 21:05 comment added Kuba hasn't forgotten Monica IOW: Real-life sock sorts are completely insensitive to what underlying algorithm you use, and you can't really choose an algorithm because your visual and motor cortex has already chosen one for you. An optimal one, as far as I can tell. The manipulation time trumps everything else. My finding is (and damn I've spent a couple of hours recording myself and analyzing the recordings): you can easily saturate your manipulators, and that's the end of it. All you need is a sufficiently big table. The CS stuff comes in only if your load doesn't fit on one table.
Mar 25 '14 at 21:05 comment added Kuba hasn't forgotten Monica This question is chock full of engineering tunnel vision. Not everything's a nail. Sorting real life socks is very dependent on the performance limitations of the human visual cognitive system and her manipulators. We can, to an extent, pattern-match socks using our parallel vision processing (visual cortex FTW). We can also, to an extent, do motion planning in parallel with acquiring the next pair of socks to pick out of the pile. The theoretic description of the algorithmic complexity of real life sock searching is nothing like what you describe.
Dec 24 '13 at 14:24 comment added Francois Bourgeois I think in this case avoidance is the best solution: I have only one type of socks and therefore it's O(n) and requires a minimum of memory... :-)
Dec 6 '13 at 11:36 comment added Marcus Laundry day is boring as it is. To eliminate the drag of sock sorting you should be doing it lazily: pour all (unmatched) socks in drawer, each morning pick two that look (kind of) the same.
Nov 28 '13 at 10:19 answer Justin Fay timeline score: 16
Nov 10 '13 at 11:25 comment added sqykly I know this doesn't answer your question in a theoretical sense, but practically speaking, nobody's looking at your socks. Not pairing them is O(k).
Oct 30 '13 at 19:47 review Close votes
Dec 17 '13 at 3:03
Oct 27 '13 at 18:45 answer maestro timeline score: 9
Oct 23 '13 at 7:56 answer Andrew Hill timeline score: 12
Oct 21 '13 at 23:42 review Suggested edits
Oct 21 '13 at 23:57
Oct 16 '13 at 12:26 comment added Erel Segal-Halevi Here is another related link: mail-archive.com/kragen-tol@canonical.org/msg00084.html
Oct 16 '13 at 12:20 comment added Erel Segal-Halevi This paper discusses a related problem : citeseerx.ist.psu.edu/viewdoc/…
Oct 8 '13 at 22:47 answer Fred Mitchell timeline score: 9
Sep 19 '13 at 13:46 comment added sfussenegger If you'd be able to duplicate socks, "hashing" wouldn't be the most efficient answer ;)
Sep 14 '13 at 4:07 comment added Thomas @Steve314 So parallelize and use multiple sock drawers.
Sep 9 '13 at 14:43 answer eldams timeline score: 7
Sep 8 '13 at 20:07 answer viper110110 timeline score: 8
Sep 7 '13 at 16:06 answer Scott Brickey timeline score: 12
Sep 7 '13 at 8:22 history reopened Peter Olson
Aaron Dufour
Blender
Terry Li
TheEvilPenguin
Sep 7 '13 at 1:51 comment added user180247 This is O(1) anyway - there's a constant limit to the number of socks that will fit in any particular washing machine or sock drawer.
Sep 7 '13 at 1:16 history closed old_timer
Lukas Eder
Sanjay T. Sharma
Eric
Sinan Ünür 		Opinion-based
Sep 6 '13 at 20:18 comment added Lee I solved this problem by only owning white knee-high socks. They all match. I could simply grab any two socks at random from the pile and they would match. I further simplify the problem by NOT pairing the socks. I have a sock drawer that I simply throw all my socks into, unpaired. I grab two at random from the drawer every morning. I've simplified it down to O(0). Can't get any simpler than that. :)
Sep 6 '13 at 16:48 comment added Mxyk Why not spawn a child and waitpid so that, as the parent, you're not even sorting any socks yourself?
Sep 6 '13 at 14:26 review Close votes
Sep 7 '13 at 1:21
Aug 22 '13 at 15:08 review Close votes
Aug 28 '13 at 3:02
Jul 11 '13 at 20:49 comment added AJMansfield Add an extra pointer to the sock class that will point to the sock's pair.
Apr 9 '13 at 3:02 review Close votes
Apr 12 '13 at 3:02
Apr 1 '13 at 19:37 answer Jim Balter timeline score: 21
Mar 29 '13 at 18:09 review Close votes
Mar 29 '13 at 21:27
Feb 17 '13 at 11:47 history reopened ThiefMaster
Feb 17 '13 at 8:24 history closed ThinkingStiff
Praveen Kumar Purushothaman
Stephen Connolly
Julius Vainora
Graviton 		off topic
Feb 16 '13 at 5:18 review Close votes
Feb 16 '13 at 10:20
Feb 8 '13 at 7:42 answer hyde timeline score: 61
Feb 6 '13 at 15:12 review Close votes
Feb 12 '13 at 3:04
Jan 29 '13 at 7:07 answer SpaceTrucker timeline score: 13
Jan 24 '13 at 19:53 answer elvitucho timeline score: 8
S Jan 24 '13 at 12:50 history notice removed CommunityBot
S Jan 24 '13 at 12:50 history unlocked CommunityBot
S Jan 23 '13 at 12:50 history notice added casperOne Comments only
S Jan 23 '13 at 12:50 history locked casperOne
Jan 23 '13 at 12:24 answer Saša timeline score: 13
Jan 23 '13 at 4:12 answer Gene timeline score: 27
Jan 23 '13 at 1:25 answer mozboz timeline score: 11
Jan 22 '13 at 22:05 answer Stephan Eggermont timeline score: 16
Jan 22 '13 at 16:32 answer Chad timeline score: 13
Jan 22 '13 at 14:04 review Close votes
Jan 23 '13 at 12:54
Jan 22 '13 at 13:33 answer Arvind timeline score: 11
Jan 21 '13 at 23:12 answer KeithS timeline score: 20
Jan 21 '13 at 20:34 comment added Nabil Kadimi Pigeonhole principle : en.wikipedia.org/wiki/Pigeonhole_principle
Jan 21 '13 at 20:16 history reopened Rachel
Sam
David Seiler
phwd
Taymon
Jan 21 '13 at 20:06 history notice removed Shog9
Jan 21 '13 at 17:35 history closed Joe
user7116
Robusto
Dancrumb
mattytommo 		not constructive
Jan 21 '13 at 16:10 review Suggested edits
Jan 21 '13 at 16:16
Jan 21 '13 at 15:23 review Close votes
Jan 21 '13 at 17:39
Jan 21 '13 at 14:47 answer D34dman timeline score: -3
Jan 21 '13 at 9:57 history reopened Andrew Grimm
Chris Morgan
Emil Ivanov
bla
Artyom
Jan 21 '13 at 5:24 history closed bmargulies
Jim Garrison
Todd A. Jacobs
Jason Coco
Anirudh Ramanathan 		not constructive
Jan 20 '13 at 22:24 review Close votes
Jan 21 '13 at 5:59
Jan 20 '13 at 20:18 answer sdcvvc timeline score: 23
Jan 20 '13 at 20:04 history reopened user616736
sdcvvc
Shog9
Jan 20 '13 at 19:37 history closed ЯegDwight
kmp
Dagg Nabbit
tereško
ДМИТРИЙ МАЛИКОВ 		off topic
Jan 20 '13 at 19:08 comment added Eric Lippert Great question! You might be interested in my article on a related problem, which is a discussion of the probability of pulling two matched socks out of the pile: blogs.msdn.com/b/ericlippert/archive/2010/03/22/…
Jan 20 '13 at 18:05 history notice added Shog9 Redditted
Jan 20 '13 at 18:03 review Close votes
Jan 20 '13 at 18:42
Jan 20 '13 at 17:54 history protected amit
Jan 20 '13 at 17:43 history edited ЯegDwight CC BY-SA 3.0
added 14 characters in body
Jan 20 '13 at 15:18 answer Samuel timeline score: 34
Jan 20 '13 at 14:28 review Close votes
Jan 20 '13 at 16:13
Jan 20 '13 at 11:21 answer dpc.pw timeline score: 604
Jan 20 '13 at 10:15 history reopened amit
Mark Harrison
Aristos
Nawaz
Hubro
Jan 20 '13 at 8:33 review Reopen votes
Jan 20 '13 at 8:42
Jan 20 '13 at 8:14 history closed JJJ
Jim G.
Lightness Races in Orbit
laurent
fbrereto 		off topic
Jan 20 '13 at 6:56 comment added doug65536 A good algorithm to do by hand might be a shift-reduce algorithm. Add a new sock to the pile randomly and as soon as you have a pair on top, "reduce" and take the pair away. Eventually you'll get most of them. Remainder can be manually handled or algorithm restarted. Not computer science in the slightest but reasonably good since you can cheat a bit and pick up the right sock sometimes.
Jan 20 '13 at 6:13 comment added Izkata By the way, this is better known (sort of) as the game of Concentration - making pairs from a large random group.
Jan 20 '13 at 4:52 comment added thang remark that if you had an infinite number of different symmetric pairs of socks (i.e. left=right), then, in fact, just picking out one of each is not possible unless you accept the axiom of choice (en.wikipedia.org/wiki/Axiom_of_choice). What consequence does this have on pairing? how is this relevant to computability? math.stackexchange.com/questions/269902/…
Jan 20 '13 at 3:34 answer guylhem timeline score: 159
Jan 19 '13 at 22:27 answer usr timeline score: 2519
Jan 19 '13 at 22:25 answer trpt4him timeline score: 11
Jan 19 '13 at 22:19 answer 1-----1 timeline score: 23
Jan 19 '13 at 21:48 answer Terry Li timeline score: 270
Jan 19 '13 at 20:40 answer andredor timeline score: 53
Jan 19 '13 at 19:58 review Close votes
Jan 20 '13 at 0:22
Jan 19 '13 at 17:54 comment added amit @MooingDuck: If you have something specific in mind, please post it, note that I do not "discard it" - this is only my initial thaughts - that might be wrong, the question itself does not forbid hashing, it only requires the algorithm to be in-place (and efficient). As said, I will also appreciate an answer that deals with the other aspects (small/large scale, and equivalence to the distinctness problem - that will show O(nlogn) is basically the best I can get without extra space)
Jan 19 '13 at 17:42 comment added Mooing Duck also, you discard hashes beccause you cant make copies, but note that its easily possible to make a hash set that doesnt need copies, both in computing and in laundry.
Jan 19 '13 at 16:59 history edited amit CC BY-SA 3.0
added 95 characters in body
Jan 19 '13 at 15:57 comment added wildplasser Yet another pigeon hole principle: if you take a subset of n/2 +1 socks, there must be at least one pair in this subset.
Jan 19 '13 at 15:53 history edited LSerni CC BY-SA 3.0
typo and unnecessary html tag
Jan 19 '13 at 15:49 answer Vilx- timeline score: 108
Jan 19 '13 at 15:42 comment added sehe Pick your favourite ordering principle (colour, texture, thickness), sort by that, pick adjacent pairs
Jan 19 '13 at 15:39 history edited amit CC BY-SA 3.0
added 61 characters in body
Jan 19 '13 at 15:37 comment added Dave I would think you could simplify it somewhat by assuming that some subset of pairs of socks are fungible; I have about six pairs of socks that are identical. Also: neat question!
Jan 19 '13 at 15:37 comment added Srinivas I use pigeon hole principle to pair exactly one from the laundry pile. I have 3 different colors of socks (Red,Blue and Green) and 2 pairs of each color. I pick up 4 number of socks each time and I always make up a pair and get to work.
Jan 19 '13 at 15:34 history asked amit CC BY-SA 3.0
toggle format

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.