It’s a laborious chore – matching up socks in a big pile of washing. They never seem to come out together, but now there’s an algorithm that promises to turn you into an efficient sock-sorting machine.
People often end up pulling out a sock, one at a time, and searching for its partner. But sorting socks this way can be a slow process.
If you only owned one pair of socks it would be fine – apart from the personal hygiene implications.
But each new pair added to the mix makes things harder in two different ways – first, you’ve got to pair up more socks, and second, each sock that you’re trying to pair up is swimming in a larger pile of unmatched socks.
Two pairs will take four times longer to match, on average, than one pair. Five pairs will take 25 times longer and 100 pairs will take 10,000 times longer, according to computer scientist and co-author of Algorithms to Live By, Prof Brian Christian.
In the book, he and co-author Tom Griffith argue that the techniques of computer science can help manage everyday situations in a logical and efficient manner, including sorting socks.
They suggest thinking of an algorithm as a recipe, a step-by-step procedure to get a specific result. If you take sorting socks as an example, the finished dish is a matching pair of socks.
The algorithm Christian recommends here is a radix sort.
“The basic idea of a radix sort is that you want to create categories apart – so let’s say colour. You would begin by just dividing all the socks into groups by colour. Let’s say you create a pile for grey socks and a pile for black socks and a pile for white socks.
Find out more
- Listen to Jordan Dunbar’s report on BBC iPlayer Radio
- More or Less is broadcast on BBC Radio 4 and the World Service
- Download the More or Less podcast
- More stories from More or Less
“Then you pick some other property, let’s say length. One of the biggest things to do to make some kind of headway is to shrink the size of the problem. So in this case we are sub-dividing these socks into these smaller groups which are then much more tractable on their own.”
A radix sort can help match socks faster than simply grabbing random ones out of the pile.
But what if you could you avoid the whole issue of sorting socks by buying a huge stash of identical black ones?
One person, Jim Bumstead, emailed us to warn against this: “Your article reminded me of a clever colleague, who, fed up with odd socks coming out of the washing machine, dumped them all and bought 12 pairs of identical ones. A few weeks later, however, he was flabbergasted to find ‘odd’ socks appearing in the wash. The reason was that socks are dyed in batches and are not necessarily made from the same wool. Some lose colour more rapidly than others, thus not remaining as pairs,” he says.
So that can take you back to square one, with an even harder job as they’re now all subtly different shades of the same colour.
And of course, there’s the ultimate sock question – you’re left with one lonely sock at the bottom of the pile with no idea what’s become of its partner. Is there a supercomputer working on that somewhere?
Article source: http://www.bbc.co.uk/news/magazine-37196037