如何有效地从一堆袜子中配对袜子?

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²/8 socks on average.

昨天我把袜子和干净的衣服配对，发现我做的方法不是很有效率。我正在做一个简单的搜索——挑选一只袜子，然后“迭代”一堆，以便找到它的一对。这需要迭代n/2 * n/4 = n2/8袜子。

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.

作为一个计算机科学家，我在想我能做些什么?排序(根据大小/颜色/…)当然是为了实现一个O(NlogN)解决方案。

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.)

给定一堆n双袜子，包含2n个元素(假设每只袜子只有一个匹配的一对)，如何有效地将它们与对数的额外空间配对?(我相信，如果需要的话，我可以记住这些信息。)

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?)
• 袜子的实际数量不是那么大，我不相信我的配偶和我有30多对。(很容易区分我的袜子和她的袜子;这也能用吗?)
• Is it equivalent to the element distinctness problem?
• 它是否等价于元素的特殊性问题?

36 个解决方案

#1

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).

所以哈希就足够了(而且更快)。

1. For each color of socks, form a pile. Iterate over all socks in your input basket and distribute them onto the color piles.
2. 每一种颜色的袜子，形成一堆。在你的输入框中重复所有的袜子，并将它们分配到颜色堆上。
3. Iterate over each pile and distribute it by some other metric (e.g. pattern) into the second set of piles
4. 遍历每一堆，并将其按其他指标(如模式)分配到第二组堆中。
5. Recursively apply this scheme until you have distributed all socks onto very small piles that you can visually process immediately
6. 递归地应用这个方案，直到你把所有的袜子都分配到很小的桩上，这样你就可以在视觉上立即处理。

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.

这种递归散列分区实际上是由SQL Server完成的，因为它需要在庞大的数据集上散列连接或散列集合。它将构建输入流分布到许多独立的分区中。该方案可对任意数量的数据和多个cpu进行线性扩展。

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.

如果您可以找到一个分配键(散列键)，您不需要递归分区，它提供了足够多的bucket，每个bucket都足够小，可以非常快地处理。不幸的是，我不认为袜子有这样的属性。

If each sock had an integer called "PairID" one could easily distribute them into 10 buckets according to PairID % 10 (the last digit).

如果每只袜子都有一个被称为“PairID”的整数，那么根据PairID % 10(最后一个数字)可以很容易地将它们分配到10个桶中。

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.)

我所能想到的最好的实际分区是创建一个堆的矩形:一个维度是颜色，另一个是模式。为什么一个矩形?因为我们需要O(1)随机存取成堆。(3D长方体也会有用，但这不是很实用。)

---

Update:

更新:

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

并行性呢?多个人类能更快地匹配袜子吗?

1. 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.
2. 最简单的并行化策略是让多个工作人员从输入框中取出袜子放到桩上。这只是放大了这么多——想象一下100个人在10堆的情况下战斗。同步成本(表现为手动冲突和人类通信)破坏效率和加速(参见通用可伸缩性法律!)这容易死锁吗?不，因为每个工人每次只需要访问一堆。只有一个“锁”，就不会出现死锁。Livelocks可能取决于人类如何协调对桩的存取。他们可能只是使用像网卡这样的随机备份，在物理层上决定什么卡可以完全访问网络线路。如果它适用于NICs，它也应该适用于人类。
3. 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.
4. 如果每个工人都有自己的一套一堆，它几乎可以无限扩展。然后，工人们可以从输入的篮子里取出大块的袜子(很少有争论，因为他们很少这样做)，而且在分发袜子的时候也不需要同步(因为他们有线程本地的堆)。最后，所有的工人都需要结合他们的打桩机。我相信，如果工人们形成了一棵汇聚树，那么可以在O(log (worker count *堆每个worker))中完成。

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)).

元素的特殊性有什么问题?由于本文所述，元素的特殊性问题可以在O(N)中得到解决。对于socks问题(同样是O(N)，如果您只需要一个分发步骤(我提出了多个步骤，仅仅是因为人类不擅长计算)，那么，如果您在md5(颜色、长度、模式、……)上分布，那么一步就足够了，即所有属性的完美散列)。

Clearly, one cannot go faster than O(N), so we have reached the optimal lower bound.

显然，一个不能比O(N)快，所以我们已经到达了最优下界。

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.

尽管输出并不完全相同(在一种情况下，只是一个布尔值)。在另一种情况下，双袜子)，渐近的复杂性是相同的。

#2

As the architecture of the human brain is completely different than a modern CPU, this question makes no practical sense.

由于人类大脑的架构与现代CPU完全不同，这个问题没有实际意义。

Humans can win over CPU algorithms using the fact that "finding a matching pair" can be one operation for a set that isn't too big.

人类可以利用“找到匹配的一对”这一事实来赢得CPU算法，这是一种不太大的集合的操作。

My algorithm:

我的算法:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

At least this is what I am using in real life, and I find it very efficient. The downside is it requires a flat surface, but it's usually abundant.

至少这是我在现实生活中使用的，而且我觉得它非常有效。缺点是它需要平坦的表面，但通常很丰富。

#3

Case 1: All socks are identical (this is what I do in real life by the way).

案例1:所有的袜子都是相同的(这是我在现实生活中所做的)。

Pick any two of them to make a pair. Constant time.

挑两个人做一对。时间常数。

Case 2: There are a constant number of combinations (ownership, color, size, texture, etc.).

案例2:有一个常数数目的组合(所有权、颜色、大小、纹理等)。

Use radix sort. This is only linear time since comparison is not required.

使用基数排序。这只是线性时间，因为不需要比较。

Case 3: The number of combinations is not known in advance (general case).

案例3:事先不知道组合的数量(一般情况)。

We have to do comparison to check whether two socks come in pair. Pick one of the O(n log n) comparison-based sorting algorithms.

我们得做个比较，看看两只袜子是成对的。选择一个O(n log n)基于比较的排序算法。

However in real life when the number of socks is relatively small (constant), these theoretically optimal algorithms wouldn't work well. It might take even more time than sequential search, which theoretically requires quadratic time.

然而，在现实生活中，当袜子的数量相对较小(常数)时，这些理论上最优的算法就不能很好地工作。它可能需要比顺序搜索更多的时间，这在理论上是需要二次时间的。

#4

Non-algorithmic answer, yet "efficient" when I do it:

非算法的答案，但当我做的时候“有效”:

• step 1) discard all your existing socks

  步骤1)丢弃所有现有的袜子。

• 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.

  步骤2)去沃尔玛，用一包10 - n包的白色和m包的黑色包装。在日常生活中不需要其他颜色。

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.

然而，有时，我不得不再次做这件事(丢失的袜子，破损的袜子等等)，而且我也不喜欢经常丢弃完美的袜子(而且我希望他们继续卖同样的袜子参考!)，所以我最近采取了不同的方法。

Algorithmic answer:

算法的回答:

Consider than if you draw only one sock for the second stack of socks, as you are doing, your odds of finding the matching sock in a naive search is quite low.

考虑一下，如果你只画一只袜子，就像你正在做的那样，你在天真的搜索中找到匹配的袜子的几率是很低的。

• So pick up five of them at random, and memorize their shape or their length.
• 所以随机挑选5个，记住它们的形状或长度。

Why five? Usually humans are good are remembering between five and seven different elements in the working memory - a bit like the human equivalent of a RPN stack - five is a safe default.

为什么五?通常，人类很好地记住了工作记忆中的5到7个不同的元素——有点像人类的RPN叠加——5是一个安全的默认值。

• Pick up one from the stack of 2n-5.

  从2n-5的堆栈中取一个。

• Now look for a match (visual pattern matching - humans are good at that with a small stack) inside the five you drew, if you don't find one, then add that to your five.

  现在寻找一个匹配(视觉模式匹配——人类擅长于一个小的堆栈)在你画的5，如果你没有找到，然后把它添加到你的5。

• Keep randomly picking socks from the stack and compare to your 5+1 socks for a match. As your stack grows, it will reduce your performance but raise your odds. Much faster.

  从堆栈中随机挑选袜子，并与你的5+1袜子相比较。当你的堆栈增长时，它会降低你的表现，但提高你的胜算。快得多。

Feel free to write down the formula to calculate how many samples you have to draw for a 50% odds of a match. IIRC it's an hypergeometric law.

你可以*写下公式来计算你需要抽取多少个样本值50%的概率。IIRC是一个超几何定律。

I do that every morning and rarely need more than three draws - but I have n similar pairs (around 10, give or take the lost ones) of m shaped white socks. Now you can estimate the size of my stack of stocks :-)

我每天早上都这样做，很少需要超过三次的抽奖——但是我有n个相似的对(大约10个，给或拿掉那些丢失的)的m型白袜子。现在你可以估计我的股票的规模:-)

BTW, I found that the sum of 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. A just-in-time works better because then you don't have to bind the socks, and there's also a diminishing marginal return (that is, you keep looking for that two or three socks that when somewhere in the laundry and that you need to finish matching your socks and you lose time on that).

顺便说一下，我发现每次我需要一双袜子的时候，整理所有袜子的交易费用的总和远远少于一次，并且把袜子绑起来。即时效果更好,因为你不必把袜子,还有一个边际报酬递减(也就是说,你继续寻找那两个或三个袜子,当在洗衣服,你需要完成匹配你的袜子和你浪费时间)。

#5

What I do is that I pick up the first sock and put it down (say, on the edge of the laundry bowl). Then I pick up another sock and check to see if it's the same as the first sock. If it is, I remove them both. If it's not, I put it down next to the first sock. Then I pick up the third sock and compare that to the first two (if they're still there). Etc.

我要做的就是拿起第一只袜子，把它放下(比如说，在洗衣碗边上)。然后我拿起另一只袜子，检查它是否和第一只袜子一样。如果是，我把它们都移走。如果不是，我把它放在第一个袜子旁边。然后我拿起第三只袜子，把它和前两个袜子做比较(如果它们还在的话)。等。

This approach can be fairly easily be implemented in an array, assuming that "removing" socks is an option. Actually, you don't even need to "remove" socks. If you don't need sorting of the socks (see below), then you can just move them around and end up with an array that has all the socks arranged in pairs in the array.

这种方法可以很容易地在数组中实现，假设“删除”袜子是一个选项。实际上，你甚至不需要“脱掉”袜子。如果你不需要对袜子进行分类(见下面)，那么你就可以移动它们，并最终得到一个数组，所有的袜子都是成对排列的。

Assuming that the only operation for socks is to compare for equality, this algorithm is basically still an n² algorithm, though I don't know about the average case (never learned to calculate that).

假设袜子的唯一操作是比较相等，这个算法基本上还是一个n2算法，虽然我不知道平均情况(从来没有学会计算)。

Sorting, of course improves efficiency, especially in real life where you can easily "insert" a sock between two other socks. In computing the same could be achieved by a tree, but that's extra space. And, of course, we're back at NlogN (or a bit more, if there are several socks that are the same by sorting criteria, but not from the same pair).

分类，当然可以提高效率，特别是在现实生活中，你可以很容易地“插入”袜子在另外两只袜子之间。在计算过程中，树可以达到同样的效果，但这是额外的空间。当然，我们又回到了NlogN(或者多一点，如果有几只袜子的排序标准是相同的，但不是同一对)。

Other than that, I cannot think of anything, but this method does seem to be pretty efficient in real life. :)

除此之外，我想不出任何东西，但这种方法在现实生活中似乎是相当有效的。:)

#6

This is asking the wrong question. The right question to ask is, why am I spending time sorting socks? How much does it cost on yearly basis, when you value your free time for X monetary units of your choice?

这是在问一个错误的问题。正确的问题是，为什么我要花时间整理袜子?当你把你的空闲时间花在你选择的X货币单位时，每年的成本是多少?

And more often than not, this is not just any free time, it's morning free time, which you could be spending in bed, or sipping your coffee, or leaving a bit early and not being caught in the traffic.

通常情况下，这不仅仅是一段空闲时间，而是早上的空余时间，你可以在床上花钱，或者喝咖啡，或者早一点离开，不要被交通堵塞。

It's often good to take a step back, and think a way around the problem.

退一步思考，思考解决问题的方法通常是好的。

And there is a way!

还有一种方法!

Find a sock you like. Take all relevant features into account: colour in different lighting conditions, overall quality and durability, comfort in different climatic conditions, and odour absorption. Also important is, they should not lose elasticity in storage, so natural fabrics are good, and they should be available in a plastic wrapping.

找一只你喜欢的袜子。考虑到所有相关的特点:不同的光照条件，整体的质量和耐久性，不同气候条件下的舒适，以及气味的吸收。同样重要的是，它们不应失去储存的弹性，所以自然的织物是好的，而且它们应该可以用塑料包装。

It's better if there's no difference between left and right foot socks, but it's not critical. If socks are left-right symmetrical, finding a pair is O(1) operation, and sorting the socks is approximate O(M) operation, where M is the number of places in your house, which you have littered with socks, ideally some small constant number.

如果左脚和右脚的袜子没有区别，那就更好了，但这并不重要。如果袜子是左右对称的，找到一对是O(1)操作，而对袜子进行排序是近似O(M)的操作，M是你房子里的位置数，你把袜子丢了，最好是一个小的常数。

If you chose a fancy pair with different left and right sock, doing a full bucket sort to left and right foot buckets take O(N+M), where N is the number of socks and M is same as above. Somebody else can give the formula for average iterations of finding the first pair, but worst case for finding a pair with blind search is N/2+1, which becomes astronomically unlikely case for reasonable N. This can be sped up by using advanced image recognition algorithms and heuristics, when scanning the pile of unsorted socks with Mk1 Eyeball.

如果你选择了一双不同的左右手袜子，那么你可以选择一个完整的桶，然后把它放在左边和右脚的桶里，然后用O(N+M)，其中N是袜子的数量，M和上面的一样。别人能给的公式的平均迭代找到第一对,但是坏的情况下寻找一对盲目搜索是N / 2 + 1,这就极可能理由合理N .这可以加快采用先进的图像识别算法和启发式,当扫描一堆无序袜子Mk1眼球。

So, an algorithm for achieving O(1) sock pairing efficiency (assuming symmetrical sock) is:

因此，实现O(1)袜子配对效率(假设对称袜子)的算法是:

1. You need to estimate how many pairs of socks you will need for the rest of your life, or perhaps until you retire and move to warmer climates with no need to wear socks ever again. If you are young, you could also estimate how long it takes before we'll all have sock-sorting robots in our homes, and the whole problem becomes irrelevant.

   你需要估计你的余生需要多少双袜子，或者直到你退休，搬到更温暖的地方，再也不用穿袜子了。如果你还年轻，你还可以估算出在我们家里，所有的机器人都需要用多久的时间来分类，整个问题变得无关紧要了。

2. You need to find out how you can order your selected sock in bulk, and how much it costs, and do they deliver.

   你需要知道如何批量订购你所选择的袜子，以及它的成本，以及它们的交付。

3. Order the socks!

   订单的袜子!

4. Get rid of your old socks.

   扔掉你的旧袜子。

An alternative step 3 would involve comparing costs of buying the same amount of perhaps cheaper socks a few pairs at a time over the years and adding the cost of sorting socks, but take my word for it: buying in bulk is cheaper! Also, socks in storage increase in value at the rate of stock price inflation, which is more than you would get on many investments. Then again there is also storage cost, but socks really do not take much space on the top shelf of a closet.

另一种方法是比较几年来买几双便宜袜子的成本，再加上整理袜子的成本，但相信我的话:批量购买更便宜!另外，袜子的储存价值会随着股票价格的上涨而增加，这比你在许多投资上得到的要多。此外，还有存储成本，但袜子在衣橱的顶层没有占用太多空间。

Problem solved. So, just get new socks, throw/donate your old ones away, and live happily ever after knowing you are saving money and time every day for the rest of your life.

问题解决了。所以，只要买一双新袜子，扔掉你的旧袜子，在知道你每天都在为你的余生节省金钱和时间之后，你就可以幸福地生活了。

#7

The theoretical limit is O(n) because you need to touch each sock (unless some are already paired somehow).

理论上的限制是O(n)，因为你需要触摸每只袜子(除非某些袜子已经配对了)。

You can achieve O(n) with radix sort. You just need to pick some attributes for the buckets.

你可以用基数排序来实现O(n)。您只需要为bucket选择一些属性。

1. First you can choose (hers, mine) - split them into 2 piles,
2. 首先你可以选择(她的，我的)-把它们分成两堆，
3. then use colors (can have any order for the colors, e.g. alphabetically by color name) - split them into piles by color (remember to keep the initial order from step 1 for all socks in the same pile),
4. 然后使用颜色(可以有任何颜色的顺序，例如按颜色名称按字母顺序排列)-按颜色将它们分割成一堆堆(记住要保留同一堆中所有袜子的第一步的初始顺序)，
5. then length of the sock,
6. 然后袜子的长度，
7. then texture, ....
8. 然后纹理,....

If you can pick a limited number of attributes, but enough attributes that can uniquely identify each pair, you should be done in O(k * n), which is O(n) if we can consider k is limited.

如果您可以选择有限数量的属性，但是足够的属性可以唯一地标识每一对，那么您应该在O(k * n)中完成，如果我们可以考虑k是有限的，那么它就是O(n)。

#8

As a practical solution:

作为一个实际的解决方案:

1. Quickly make piles of easily distinguishable socks. (Say by color)
2. 快速做一堆容易辨认的袜子。(说的颜色)
3. Quicksort every pile and use the length of the sock for comparison. As a human you can make a fairly quick decision which sock to use to partition that avoids worst case. (You can see multiple socks in parallel, use that to your advantage!)
4. 快速排序每一堆，并使用袜子的长度进行比较。作为一个人，你可以做一个相当快速的决定，用袜子来划分，避免最坏的情况。(你可以同时看到多个袜子，这对你有好处!)
5. Stop sorting piles when they reached a threshold at which you are comfortable to find spot pairs and unpairable socks instantly
6. 当他们到达一个门槛时，不要分拣堆，这样你就能立刻找到一双合适的袜子和一双不穿裤子的袜子。

If you have 1000 socks, with 8 colors and an average distribution, you can make 4 piles of each 125 socks in c*n time. With a threshold of 5 socks you can sort every pile in 6 runs. (Counting 2 seconds to throw a sock on the right pile it will take you little under 4 hours.)

如果你有1000只袜子，有8种颜色和平均分布，你可以在c*n时间内每125只袜子做4堆。有了5只袜子的门槛，你可以在6次跑步中对每一堆进行排序。(用2秒的时间把一只袜子扔到正确的堆上，你需要4个小时的时间。)

If you have just 60 socks, 3 colors and 2 sort of socks (yours / your wife's) you can sort every pile of 10 socks in 1 runs (Again threshold = 5). (Counting 2 seconds it will take you 2 min).

如果你只有60只袜子，3种颜色和2种袜子(你的/你的妻子的)，你可以在1次跑步中对每一堆10只袜子进行分类(同样的阈值= 5)。(2秒的时间，你需要2分钟)。

The initial bucket sorting will speed up your process, because it divides your n socks into k buckets in c*n time so than you will only have to do c*n*log(k) work. (Not taking into account the threshold). So all in all you do about n*c*(1 + log(k)) work, where c is the time to throw a sock on a pile.

最初的bucket排序将加速您的进程，因为它在c*n时将您的n个袜子分成k个桶，所以您只需要做c*n*log(k)工作。(不考虑门槛)。所以，在你所做的所有事情中，你都要做n*c*(1 + log(k))的工作，c是把袜子扔到一堆上的时间。

This approach will be favourable compared to any c*x*n + O(1) method roughly as long as log(k) < x - 1.

这种方法与任何c*x*n + O(1)方法相比都是有利的，只要log(k) < x - 1。

---

In computer science this can be helpful: We have a collection of n things, an order on them (length) and also an equivalence relation (extra information, for example the color of socks). The equivalence relation allows us to make a partition of the original collection, and in every equivalence class our order is still maintained. The mapping of a thing to it's equivalence class can be done in O(1), so only O(n) is needed to assign each item to a class. Now we have used our extra information and can proceed in any manner to sort every class. The advantage is that the data sets are already significantly smaller.

在计算机科学中，这是有帮助的:我们有n个东西的集合，一个在它们(长度)上的顺序，还有一个等价关系(例如，额外的信息，例如袜子的颜色)。等价关系允许我们对原始集合进行划分，在每个等价类中，我们的顺序仍然保持。一个东西到它的等价类的映射可以在O(1)中完成，所以只需要O(n)将每个条目分配给一个类。现在我们已经使用了我们的额外信息，并且可以以任何方式对每个类进行排序。其优点是，数据集已经大大缩小了。

The method can also be nested, if we have multiple equivalence relations -> make colour piles, than within every pile partition on texture, than sort on length. Any equivalence relation that creates a partition with more than 2 elements that have about even size will bring a speed improvement over sorting (provided we can directly assign a sock to its pile), and the sorting can happen very quickly on smaller data sets.

该方法也可以嵌套，如果我们有多个等价关系——>做颜色桩，而不是在每一堆的纹理上，比在长度上排序。任何等价关系创建一个包含两个以上元素的分区，它的大小将会比排序的速度更快(只要我们可以直接分配一个袜子到它的堆上)，并且在较小的数据集上，排序就会很快发生。

#9

This question is actually deeply philosophical. At heart it's about whether the power of people to solve problems (the "wetware" of our brains) is equivalent to what can be accomplished by algorithms.

这个问题其实很有哲理。在本质上，它是关于人们解决问题的能力(我们的大脑的“wetware”)是否等同于可以通过算法完成的事情。

An obvious algorithm for sock sorting is:

袜子分类的一个明显的算法是:

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

Now the computer science in this problem is all about the steps

现在这个问题的计算机科学是关于步骤的。

1. "if s pairs with a sock t in N". How quickly can we "remember" what we've seen so far?
2. “如果s对有一个袜子t在N”。我们能多快“记住”到目前为止所看到的?
3. "remove t from N" and "add s to N". How expensive is keeping track of what we've seen so far?
4. “从N中删除t”和“添加s到N”。追踪到目前为止我们看到的东西有多贵?

Human beings will use various strategies to effect these. Human memory is associative, something like a hash table where feature sets of stored values are paired with the corresponding values themselves. For example, the concept of "red car" maps to all the red cars a person is capable of remembering. Someone with a perfect memory has a perfect mapping. Most people are imperfect in this regard (and most others). The associative map has a limited capacity. Mappings may bleep out of existence under various circumstances (one beer too many), be recorded in error ("I though her name was Betty, not Nettie"), or never be overwritten even though we observe that the truth has changed ("dad's car" evokes "orange Firebird" when we actually knew he'd traded that in for the red Camaro).

人类将使用各种各样的策略来影响这些。人的记忆是有关联的，就像一个哈希表，在这里，存储值的特征集与相应的值本身成对出现。例如，“红色汽车”的概念映射到一个人能够记住的所有红色汽车。拥有完美记忆的人拥有完美的映射。大多数人在这方面都是不完美的(还有大多数人)。联想图的容量有限。映射可能会发出哔哔声的存在在不同的情况下(一个啤酒太多),被记录在错误(“我想她的名字是贝蒂,不是内蒂”),或者从来没有被覆盖,即使我们观察到事实改变了(“爸爸的车”唤起“橙色火鸟”当我们知道他的交易,在红色大黄蜂)。

In the case of socks, perfect recall means looking at a sock s always produces the memory of its sibling t, including enough information (where it is on the ironing board) to locate t in constant time. A person with photographic memory accomplishes both 1 and 2 in constant time without fail.

在袜子的例子中，完美的回忆意味着看袜子总是能产生它的兄弟姐妹的记忆，包括足够的信息(它在烫衣板上)在固定的时间里定位t。一个具有照相记忆的人在不变的时间内完成了1和2。

Someone with less than perfect memory might use a few commonsense equivalence classes based on features within his capability to track: size (papa, mama, baby), color (greenish, redish, etc.), pattern (argyle, plain, etc.), style (footie, knee-high, etc.). So the ironing board would be divided into sections for the categories. This usually allows the category to be located in constant time by memory, but then a linear search through the category "bucket" is needed.

没有完美记忆的人可能会使用一些基于他能力范围内的一些常识的对等类:大小(爸爸、妈妈、宝宝)、颜色(绿色、重口味等)、图案(菱形、平纹等)、样式(脚、膝等)。所以烫衣板会被分成不同的类别。这通常允许类在内存中处于常量时间，但是需要通过类别“bucket”进行线性搜索。

Someone with no memory or imagination at all (sorry) will just keep the socks in one pile and do a linear search of the whole pile.

没有记忆或想象力的人(对不起)只会把袜子放在一堆里，然后对整堆进行线性搜索。

A neat freak might use numeric labels for pairs as someone suggested. This opens the door to a total ordering, which allows the human to use exactly the same algorithms we might with a CPU: binary search, trees, hashes, etc.

一个整洁的怪物可能会像有人建议的那样使用数字标签。这打开了一个总排序的门，它允许人类使用与CPU完全相同的算法:二进制搜索、树、散列等等。

So the "best" algorithm depends on the qualities of the wetware/hardware/software that is running it and our willingness to "cheat" by imposing a total order on pairs. Certainly a "best" meta-algorithm is to hire the worlds best sock-sorter: a person or machine that can aquire and quickly store a huge set N of sock attribute sets in a 1-1 associative memory with constant time lookup, insert, and delete. Both people and machines like this can be procured. If you have one, you can pair all the socks in O(N) time for N pairs, which is optimal. The total order tags allow you to use standard hashing to get the same result with either a human or hardware computer.

因此，“最佳”算法取决于运行它的wetware/硬件/软件的质量，以及我们是否愿意“欺骗”，通过对双成对执行一个总的订单。当然，一个“最佳”的元算法是雇佣世界上最好的soc -sorter:一个人或机器，它可以在1-1联想内存中存储一个巨大的set N，并将其存储在一个1-1的关联内存中，并使用常量时间查找、插入和删除。像这样的人和机器都可以买到。如果你有一个，你可以把所有的袜子在O(N)的时间对N对，这是最优的。总订单标记允许您使用标准的散列，以获得与人或硬件计算机相同的结果。

#10

You are trying to solve the wrong problem.

你正试图解决一个错误的问题。

Solution 1: Each time you put dirty socks in your laundry basket, tie them in a little knot. That way you will not have to do any sorting after the washing. Think of it like registering an index in a Mongo database. A little work ahead for some CPU savings in the future.

解决方案1:每次你把脏袜子放进洗衣篮，把它们打成一个小结。这样你就不用在洗衣服后做任何分类了。就像在Mongo数据库中注册索引一样。在未来的一些CPU节约方面还有一些工作要做。

Solution 2: If it's winter, you don't have to wear matching socks. We are programmers. Nobody needs to know, as long as it works.

解决方案2:如果是冬天，你就不用穿配套的袜子了。我们是程序员。没有人需要知道，只要它有效。

Solution 3: Spread the work. You want to perform such a complex CPU process asynchronously, without blocking the UI. Take that pile of socks and stuff them in a bag. Only look for a pair when you need it. That way the amount of work it takes is much less noticeable.

解决方案3:展开工作。您希望异步地执行这样一个复杂的CPU进程，而不会阻塞UI。拿起那堆袜子，把它们塞进袋子里。只有在需要的时候才找一双。这样做的工作量就不那么明显了。

Hope this helps!

希望这可以帮助!

#11

Here's an Omega(n log n) lower bound in comparison based model. (The only valid operation is comparing two socks.)

这是一个基于比较的模型下的(n log n)下界。(唯一有效的操作是比较两只袜子。)

Suppose that you know that your 2n socks are arranged this way:

假设你知道你的2n袜子是这样排列的:

p₁ p₂ p₃ ... p_n p_f(1) p_f(2) ... p_f(n)

p1 p2 p3……pn pf(1)pf(2)……pf(n)

where f is an unknown permutation of the set {1,2,...,n}. Knowing this cannot make the problem harder. There are n! possible outputs (matchings between first and second half), which means you need log(n!) = Omega(n log n) comparisons. This is obtainable by sorting.

其中f是集合{1,2，…，n}的未知排列。知道这一点并不能使问题变得更加困难。有n !可能的输出(第一和第二部分之间的匹配)，这意味着您需要log(n!) = (n log n)比较。这是通过排序得到的。

Since you are interested in connections to element distinctness problem: proving the Omega(n log n) bound for element distinctness is harder, because the output is binary yes/no. Here, the output has to be a matching and the number of possible outputs suffices to get a decent bound. However, there's a variant connected to element distinctness. Suppose you are given 2n socks and wonder if they can be uniquely paired. You can get a reduction from ED by sending (a₁, a₂, ..., a_n) to (a₁, a₁, a₂, a₂, ..., a_n, a_n). (Parenthetically, the proof of hardness of ED is very interesting, via topology.)

因为您对元素的特殊性问题有兴趣:证明对元素的特殊性约束的Omega(n log n)是比较困难的，因为输出是二进制的yes/no。在这里，输出必须是匹配的，并且可能的输出数量足以得到一个适当的约束。然而，有一种与元素的特殊性相关联的变体。假设你给了2n只袜子，想知道它们是否可以单独配对。你可以通过发送(a1, a2，…，a) to (a1, a1, a2, a2，…一个,一个)。(顺便说一下，ED的硬度证明很有趣，通过拓扑学。)

I think that there should be an Omega(n²) bound for the original problem if you allow equality tests only. My intuition is: Consider a graph where you add an edge after a test, and argue that if the graph is not dense the output is not uniquely determined.

我认为如果你只允许等式测试，就应该有一个原始问题的欧米茄(n2)。我的直觉是:考虑一个在测试后添加一条边的图形，并认为如果图形不稠密，输出就不是唯一确定的。

#12

Cost: Moving socks -> high, finding/search socks in line -> small

成本:移动袜子->高，发现/搜索袜子在线->小。

What we want to do is reduce the number of moves, and compensate with the number of searches. Also, we can utilize the multithreded environment of the Homo Sapiens to hold more things in the descision cache.

我们要做的是减少移动的数量，并通过搜索的数量来弥补。同时，我们也可以利用智人的多谷环境来容纳更多的东西在descision缓存中。

X = Yours, Y = Your spouses

X =你的，Y =你的配偶。

From pile A of all socks:

从一堆袜子:

Pick two socks, place corresponding X sock in X line, and Y sock in Y line at next available position.

选择两只袜子，将相应的X线袜子放在X线上，然后在Y线上放置Y线。

Do until A is empty.

直到A是空的。

For each line X and Y

对于每一行X和Y。

1. Pick the first sock in line, search along the line until it finds the corresponding sock.

   选择第一个袜子，沿着这条线搜索直到找到相应的袜子。

2. Put into the corresponding finished line of socks.

   放入相应的成品袜子。

3. Optional While you are searching the line and and the current sock you are looking at is identical to the previous, do step 2 for these socks.
4. 当你在搜索这条线的时候，你所看到的袜子和之前的袜子是一样的。

Optionally to step one, you pick up two sock from that line instead of two, as the caching memory is large enough we can quickly identify if either sock matches the current one on the line you are observing. If you are fortunate enough to have three arms, you could possibly parse three socks at the same time given that the memory of the subject is large enough.

可以选择第一步，从该行中选择两个袜子，而不是两个，因为缓存内存足够大，我们可以快速确定是否有一个袜子匹配当前在线上的一个。如果你足够幸运拥有三个手臂，那么你可以同时解析三个袜子，因为这个主题的记忆足够大。

Do until both X and Y is empty.

直到X和Y都为空。

Done

完成

However, as this have simillar complexity as selection sort, the time taken is far less due to the speeds of I/O(moving socks) and search(searching the line for a sock).

然而，由于这是一种比较复杂的选择排序，所花的时间要少得多，因为我/O(移动的袜子)和搜索的速度(寻找袜子的线)。

#13

This is how I actually do it, for p pairs of socks (n = 2p individual socks):

这就是我怎么做的，对于p对袜子(n = 2p单独的袜子):

• Grab a sock at random from the pile.
• 从堆里随便拿一只袜子。
• For the first sock, or if all previously-chosen socks have been paired, simply place the sock into the first "slot" of an "array" of unpaired socks in front of you.
• 对于第一个袜子，或者如果所有之前选择的袜子已经配对，只需把袜子放在你面前的“排列”袜子的第一个“插槽”。
• If you have one or more selected unpaired socks, check your current sock against all the unpaired socks in the array.
  • It is possible to separate socks into general classes or types (white/black, ankle/crew, athletic/dress) when building your array, and "drill-down" to only compare like-for-like.
  • 在构建你的数组时，你可以将袜子分为普通类或类型(白色/黑色、脚踝/团队、运动/服装)，而“钻取”则只比较类似。
  • If you find an acceptable match, put both socks together and remove them from the array.
  • 如果你找到一个可以接受的匹配，把两个袜子放在一起，然后把它们从数组中删除。
  • If you do not, put the current sock into the first open slot in the array.
  • 如果没有，将当前的袜子放入数组的第一个开槽中。
• 如果你有一个或更多的未配对的袜子，检查你当前的袜子与所有未配对的袜子在数组。在构建你的数组时，你可以将袜子分为普通类或类型(白色/黑色、脚踝/团队、运动/服装)，而“钻取”则只比较类似。如果你找到一个可以接受的匹配，把两个袜子放在一起，然后把它们从数组中删除。如果没有，将当前的袜子放入数组的第一个开槽中。
• Repeat with every sock.
• 重复每只袜子。

The worst-case scenario of this scheme is that every pair of socks is different enough that it must be matched exactly, and that the first n/2 socks you pick are all different. This is your O(n²) scenario, and it's extremely unlikely. If the number of unique types of sock t is less than the number of pairs p = n/2, and the socks in each type are alike enough (usually in wear-related terms) that any sock of that type can be paired with any other, then as I inferred above, the maximum number of socks you will ever have to compare to is t, after which the next one you pull will match one of the unpaired socks. This scenario is much more likely in the average sock drawer than the worst-case, and reduces the worst-case complexity to O(n*t) where usually t << n.

这个方案最糟糕的情况是，每双袜子都是不同的，它必须完全匹配，而且你挑选的第一个n/2袜子都是不同的。这是您的O(n2)场景，非常不可能。如果t独特类型的袜子的数量小于对p = n / 2的数量,和每种类型的袜子都足够(通常wear-related而言),任何类型的袜子可以搭配任何其他,然后当我推断,袜子的最大数量你所要比较的是t,之后下一个您将匹配一个未配对的袜子。这一场景在一般的袜子抽屉中比最坏的情况下更有可能发生，并将最坏情况的复杂度降低到通常t << n。

#14

Real world approach:

现实世界的方法:

As rapidly as possible, remove socks from the unsorted pile one at a time and place in piles in front of you. The piles should be arranged somewhat space-efficiently, with all socks pointing the same direction; the number of piles is limited by the distance you can easily reach. The selection of a pile on which to put a sock should be -- as rapidly as possible -- by putting a sock on a pile of apparently like socks; the occasional type I (putting a sock on a pile it doesn't belong to) or type II (putting a sock in its own pile when there's an existing pile of like socks) error can be tolerated -- the most important consideration is speed. Once all the socks are in piles, rapidly go through the multi-sock piles creating pairs and removing them (these are heading for the drawer). If there are non-matching socks in the pile, re-pile them to their best (within the as-fast-as-possible constraint) pile. When all the multi-sock piles have been processed, match up remaining pairable socks that weren't paired due to type II errors. Whoosh, you're done -- and I have a lot of socks and don't wash them until a large fraction are dirty. Another practical note: I flip the top of one of a pair of socks down over the other, taking advantage of their elastic properties, so they stay together while being transported to the drawer and while in the drawer.

尽可能快地把袜子从未分类的堆中取出，放在你面前的堆里。这些桩应该在一定的空间内布置，所有的袜子都指向同一个方向;桩的数量受限于你能轻易到达的距离。把袜子放在一堆像袜子一样的东西上，尽可能快地把袜子放进去。有时我(把一只袜子放在一堆它不属于)或II型(当存在一堆像袜子一样的东西时，把袜子放在自己的堆里)是可以容忍的——最重要的考虑是速度。一旦所有的袜子都堆成一堆，快速地穿过多只袜子堆，创造成对并把它们移走(这些都是往抽屉里放的)。如果在堆中有不匹配的袜子，将它们重新堆到最好的(在尽可能快的限制内)。当所有的多袜子堆被处理后，将剩余的可穿的袜子配对，因为第二类错误而没有配对。哇，你做完了，我有很多袜子，直到有很大一部分脏了才洗。另一个实用的注意事项是:我把一双袜子的顶部压在另一只袜子上，利用它们的弹性性能，这样它们就会在被运送到抽屉时，在抽屉里的时候呆在一起。

#15

From your question it is clear you don't have much actual experience with laundry :). You need an algorithm that works well with a small number of non-pairable socks.

从你的问题来看，很明显你没有多少实际的洗衣经验:)。你需要一种算法，它能很好地处理少量的非成对的短袜。

The answers till now don't make good use of our human pattern recognition capabilities. The game of Set provides a clue of how to do this well: put all socks in a two-dimensional space so you can both recognize them well and easily reach them with your hands. This limits you to an area of about 120 * 80 cm or so. From there select the pairs you recognize and remove them. Put extra socks in the free space and repeat. If you wash for people with easily recognizable socks (small kids come to mind), you can do a radix sort by selecting those socks first. This algorithm works well only when the number of single socks is low

到目前为止，答案还不能很好地利用我们的人类模式识别能力。游戏的设置提供了一个如何做好这个的线索:把所有的袜子放在一个二维空间里，这样你就能很好地认出他们，并且用你的手轻松地到达他们。这限制了你大约120 * 80厘米左右的区域。从那里选择你认识并删除它们的对。把多余的袜子放在*空间，然后重复。如果你用容易辨认的袜子来清洗，你可以先选择那些袜子。这种算法只有在单只袜子数量少的情况下才有效。

#16

Pick up a first sock and place it on a table. Now pick another sock; if it matches the first picked, place it on top of the first. If not, place it on the table a small distance from the first. Pick a third sock; if it matches either of the previous two, place it on top of them or else place it a small distance from the third. Repeat until you have picked up all the socks.

拿起第一只袜子放在桌子上。现在选择另一个袜子;如果它匹配第一个选择，将它放在首位。如果没有的话，把它放在桌子上与第一个小的距离。选择第三个袜子;如果它与前两个相匹配，把它放在它们的上面，或者把它放在离第三个小距离的地方。重复，直到你捡起所有的袜子。

#17

In order to say how efficient it is to pair socks from a pile, we have to define the machine first, because the pairing isn't done whether by a turing nor by a random access machine, which are normally used as the basis for an algorithmic analysis.

为了说明对一堆袜子配对是多么有效，我们首先要定义机器，因为配对不是由图灵或随机存取机器来完成的，这通常被用作算法分析的基础。

The machine

The machine is an abstraction of a the real world element called human being. It is able to read from the environment via a pair of eyes. And our machine model is able to manipulate the environment by using 2 arms. Logical and arithmetic operations are calculated using our brain (hopefully ;-)).

机器是一个抽象的现实世界的元素，被称为人类。它可以通过一对眼睛从环境中读取信息。我们的机器模型可以使用2个手臂来操纵环境。逻辑运算和算术运算是用我们的大脑计算的(但愿如此)。

We also have to consider the intrinsic runtime of the atomic operations that can be carried out with these instruments. Due to physical constraints, operations which are carried out by an arm or eye have non constant time complexity. This is because we can't move an endlessly large pile of socks with an arm nor can an eye see the top sock on an endlessly large pile of socks.

我们还必须考虑可以用这些仪器进行的原子操作的内在运行时。由于物理的限制，由手臂或眼睛进行的操作具有非恒定的时间复杂度。这是因为我们不能用一只手臂不停地移动一大堆袜子，也不能让一只眼睛看到一大堆袜子上的袜子。

However mechanical physics give us some goodies as well. We are not limited to move at most one sock with an arm. We can move a whole couple of them at once.

不过，机械物理学也给了我们一些好处。我们不局限于用一只手臂移动最多一只袜子。我们可以同时移动一对。

So depending on the previous analysis following operations should be used in descending order:

因此，根据之前的分析，下列操作应按降序使用:

• logical and arithmetic operations
• 逻辑和算术运算
• environmental reads
• 环境读取
• environmental modifications
• 环境的修改

We can also make use of the fact that people only have a very limited amount of socks. So an environmental modification can involve all socks in the pile.

我们还可以利用人们只有非常有限的袜子的事实。所以环境改造可以让所有的袜子都堆在一起。

The algorithm

So here is my suggestion:

这就是我的建议:

1. Spread all socks in the pile over the floor.
2. 把所有的袜子都铺在地板上。
3. Find a pair by looking at the socks on the floor.
4. 通过看地板上的袜子找到一双。
5. Repeat from 2 until no pair can be made.
6. 重复从2到没有配对。
7. Repeat from 1 until there are no socks on the floor.
8. 重复一遍，直到地板上没有袜子。

Operation 4 is necessary, because when spreading socks over the floor some socks may hide others. Here is the analysis of the algorithm:

操作4是必要的，因为当把袜子铺在地板上时，一些袜子可能会隐藏其他袜子。下面是对算法的分析:

The analysis

The algorithm terminates with high probability. This is due to the fact that one is unable to find pairs of socks in step number 2.

该算法具有较高的概率。这是由于在第二步中不能找到双袜子的事实。

For the following runtime analysis of pairing n pairs of socks, we suppose that at least half of the 2n socks aren't hidden after step 1. So in the average case we can find n/2 pairs. This means that the loop is step 4 is executed O(log n) times. Step 2 is executed O(n^2) times. So we can conclude:

对于以下对n对袜子配对的运行时分析，我们假设在第1步之后，至少有一半的2n袜子不是隐藏的。一般情况下，我们可以找到n/2对。这意味着循环是第4步执行O(log n)次。步骤2执行O(n 2)次。所以我们可以得出结论:

• The algorithm involves O(ln n + n) environmental modifications (step 1 O(ln n) plus picking every pair of sock from the floor)
• 该算法涉及到O(ln n + n)环境修改(步骤1 O(ln n) +从地板上挑选每一双袜子)
• The algorithm involves O(n^2) environmental reads from step 2
• 算法涉及到O(n ^ 2)环境读取步骤2
• The algorithm involves O(n^2) logical and arithmetic operations for comparing a sock with another in step 2
• 算法涉及到O(n ^ 2)逻辑和算术运算比较袜子在步骤2中与另一个

So we have a total runtime complexity of O(r*n^2 + w*(ln n + n)) where r and w are the factors for environmental read and environmental write operations respectively for a reasonable amount of socks. The cost of the logical and arithmetical operations are omitted, because we suppose that it takes a constant amount of logical and arithmetical operations to decide whether 2 socks belong to the same pair. This may not be feasible in every scenario.

因此，我们有一个总的运行时复杂度为O(r*n 2 + w*(ln n + n))，其中r和w分别是环境读和环境写操作的因素，分别为合理数量的袜子。逻辑运算和算术运算的成本被省略了，因为我们假设，需要一个常数的逻辑运算和算术运算来决定两个袜子是否属于同一对。这在任何情况下都不可行。

#18

List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

#19

I came out with another solution which would not promise fewer operations, neither less time consumption, but it should be tried to see if it can be a good-enough heuristic to provide less time consumption in huge series of sock pairing.

我提出了另一种解决方案，它不能保证更少的操作，更少的时间消耗，但是应该试着去看看它是否可以成为一个足够好的启发，以减少大量的袜子配对的时间消耗。

Preconditions: There is no guarantee that there are the same socks. If they are of the same color it doesn't mean they have the same size or pattern. Socks are randomly shuffled. There can be odd number of socks (some are missing, we don't know how many). Prepare to remember a variable "index" and set it to 0.

前提条件:不能保证有相同的袜子。如果它们是相同的颜色，并不意味着它们的大小或图案相同。袜子是随机打乱。袜子的数量可能是奇数(有些丢失了，我们不知道有多少)。准备记住一个变量“索引”，并将其设置为0。

The result will have one or two piles: 1. "matched" and 2. "missing"

结果将有一或两堆:1。“匹配”和2。“失踪”

Heuristic:

启发:

1. Find most distinctive sock.
2. 找到最有特色的袜子。
3. Find its match.
4. 找到自己的比赛。
5. If there is no match, put it on the "missing" pile.
6. 如果没有匹配，就把它放在“丢失”的堆上。
7. Repeat from 1. until there are no more most distinctive socks.
8. 重复从1。直到再也没有最与众不同的袜子。
9. If there are less then 6 socks, go to 11.
10. 如果少了6只袜子，就去11个。
11. Pair blindly all socks to its neighbor (do not pack it)
12. 盲目地把所有的袜子送给邻居(不要打包)
13. Find all matched pairs, pack it and move packed pairs to "matched" pile; If there were no new matches - increment "index" by 1
14. 找到所有匹配的配对，将它打包并移动到“匹配”的堆中;如果没有新的匹配-增加“索引”1。
15. If "index" is greater then 2 (this could be value dependent on sock number because with greater number of socks there are less chance to pair them blindly) go to 11
16. 如果“索引”更大，那么2(这可能是依赖于袜子编号的值，因为有更多的袜子，就没有机会盲目地将它们配对)到11。
17. Shuffle the rest
18. 洗牌其余
19. Go to 1
20. 去1
21. Forget "index"
22. 忘记“指数”
23. Pick a sock
24. 选择一个袜子
25. Find its pair
26. 找到自己的一对
27. If there is no pair for the sock, move it to the "missing" pile
28. 如果没有一双袜子，把它移到“丢失的”一堆。
29. If match found pair it, pack pair and move it to the "matched" pile
30. 如果匹配找到对它，包对并移动到“匹配”桩。
31. If there are still more then one socks go to 12
32. 如果还有更多的话，那么一只袜子可以卖到12只。
33. If there is just one left go to 14
34. 如果只剩下一个14。
35. Smile satisfied :)
36. 微笑满意:)

Also, there could be added check for damaged socks also, as if the removal of those. It could be inserted between 2 and 3, and between 13 and 14.

此外，还可以增加对受损袜子的检查，就像去除这些一样。它可以插入2到3之间，13到14之间。

I'm looking forward to hear about any experiences or corrections.

我期待听到任何经验或更正。

#20

Socks, whether real ones or some analogous data structure, would be supplied in pairs.

袜子，不管是真实的还是类似的数据结构，都是成对供应的。

The simplest answer is prior to allowing the pair to be separated, a single data structure for the pair should have been initialized that contained a pointer to the left and right sock, thus enabling socks to be referred to directly or via their pair. A sock may also be extended to contain a pointer to its partner.

最简单的答案是，在允许这对组合被分离之前，对这对组合的一个单独的数据结构应该被初始化，其中包含一个指向左右袜子的指针，从而使袜子可以直接或通过它们的对来引用。也可以将短袜扩展以包含指向其伙伴的指针。

This solves any computational pairing problem by removing it with a layer of abstraction.

这解决了任何计算配对问题，通过去除一个抽象层。

Applying the same idea to the practical problem of pairing socks, the apparent answer is: don't allow your socks to ever be unpaired. Socks are provided as a pair, put in the drawer as a pair (perhaps by balling them together), worn as a pair. But the point where unpairing is possible is in the washer, so all that's required is a physical mechanism that allows the socks to stay together and be washed efficiently.

把同样的想法应用到配对袜子的实际问题上，很明显的答案是:不要让你的袜子从来没有配对过。袜子是一对的，放在抽屉里作为一对(也许是把它们放在一起)，作为一对穿。但是，在洗衣机里，不配对是可能的，所以所有需要的是一个物理机制，让袜子保持在一起，并被有效地清洗。

There are two physical possibilities:

有两种物理可能性:

For a 'pair' object that keeps a pointer to each sock we could have a cloth bag that we use to keep the socks together. This seems like massive overhead.

对于一个“pair”对象，每个袜子上都有一个指针，我们可以用一个布袋把袜子放在一起。这似乎是巨大的开销。

But for each sock to keep a reference to the other, there is a neat solution: a popper (or a 'snap button' if you're American), such as these:

但是，对于每只袜子来说，有一个简洁的解决方案:一个popper(如果你是美国人的话，一个“snap”按钮)，比如:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

Then all you do is snap your socks together right after you take them off and put them in your washing basket, and again you've removed the problem of needing to pair your socks with a physical abstraction of the 'pair' concept.

然后，当你把袜子拿下来放到洗衣篮里时，你就会把袜子合在一起，这样你就不用再把袜子和“pair”这个概念进行物理抽象了。

#21

When I sort socks, I do an approximate radix sort, dropping socks near other socks of the same colour/pattern type. Except in the case when I can see an exact match at/near the location I'm about to drop the sock I extract the pair at that point.

当我整理袜子的时候，我做了一个近似的基数排序，把袜子扔到同颜色/图案类型的其他袜子附近。除非我能在附近看到一个精确的匹配，否则我要把袜子丢到那个点。

Almost all the other algorithms (including the top scoring answer by usr) sort, then remove pairs. I find that, as a human, it is better to minimize the number of socks being considered at one time.

几乎所有其他算法(包括usr的最高得分答案)排序，然后删除对。我发现，作为一个人，最好尽量减少一次考虑袜子的数量。

I do this by:

我这样做的:

1. Picking a distinctive sock (whatever catches my eye first in the pile).
2. 挑选一只与众不同的袜子(无论什么东西在我的眼睛里最先引起注意)。
3. Starting a radix sort from that conceptual location by pulling socks from the pile based on similarity to that one.
4. 从这个概念的位置开始从这个概念的位置开始，从与那一堆的相似性中提取袜子。
5. Place the new sock near into the current pile, with a distance based on how different it is. If you find yourself putting the sock on top of another because it is identical, form the pair there, and remove them. This means that future comparisons take less effort to find the correct place.
6. 将新袜子放在当前的桩附近，并根据不同的位置进行距离。如果你发现自己把袜子放在另一个上面，因为它是相同的，在那里形成一对，并把它们移走。这意味着未来的比较需要更少的努力去找到正确的地方。

This takes advantage of the human ability to fuzzy-match in O(1) time, which is somewhat equivalent to the establishment of a hash-map on a computing device.

这充分利用了在O(1)时间内进行模糊匹配的能力，这在某种程度上相当于在计算设备上建立了hashmap。

By pulling the distinctive socks first, you leave space to "zoom" in on the features which are less distinctive, to begin with.

先把与众不同的袜子拉出来，你就可以让空间“变焦”，开始时的特征就不那么明显了。

After eliminating the fluro coloured, the socks with stripes, and the three pairs of long socks, you might end up with mostly white socks roughly sorted by how worn they are.

去掉了fluro颜色的袜子、条纹的袜子和三双长筒袜之后，你可能会发现大部分都是白色的袜子，基本上都是根据它们的磨损程度来分类的。

At some point, the differences between socks are small enough that other people won't notice the difference, and any further matching effort is not needed.

在某种程度上，袜子之间的差异足够小，以至于其他人不会注意到它们之间的差异，而任何进一步的匹配都是不需要的。

#22

Whenever you pick up a sock, put it in one place. Then the next sock you pick up, if it doesn't match the first sock, set it beside the first one. If it does, there's a pair. This way it doesn't really matter how many combinations there are, and there are only two possibilities for each sock you pick up -- either it has a match that's already in your array of socks, or it doesn't, which means you add it to a place in the array.

每当你拿起一只袜子，把它放在一个地方。然后你捡起的下一只袜子，如果它不匹配第一只袜子，把它放在第一个袜子旁边。如果有，就有一对。这种方式并不影响有多少种组合，每只袜子只可能有两种可能——要么它有一根已经在你的袜子里的匹配，要么它没有，这意味着你把它添加到数组中的一个位置。

This also means that you will almost certainly never have all your socks in the array, because socks will get removed as they're matched.

这也意味着你几乎肯定不会把你所有的袜子都放在这个数组里，因为袜子会在匹配的时候被移除。

#23

Consider a hash-table of size 'N'.

考虑一个大小为N的哈希表。

If we assume normal distribution, then the estimated number of 'insertions' to have atleast one sock mapped to one bucket is NlogN (ie, all buckets are full)

如果我们假设正态分布，那么至少有一个被映射到一个桶的“插入”的估计数是NlogN(即所有的桶都是满的)

I had derived this as a part of another puzzle,but I would be happy to be proven wrong. Here's my blog article on the same

我把这作为另一个谜题的一部分，但我很高兴被证明是错误的。这是我的博客文章。

Let 'N' correspond to an approximate upper-bound on the number of number of unique colors/pattern of socks that you have.

让'N'对应于你所拥有的袜子的独特颜色/图案数目的近似上限。

Once you have a collision(a.k.a : a match) simply remove that pair of socks. Repeat the same experiment with the next batch of NlogN socks. The beauty of it is that you could be making NlogN parallel comparisons(collision-resolution) because of the way the human mind works. :-)

一旦发生碰撞(a.k。a:火柴)只要把那双袜子脱掉。对下一批NlogN袜子重复同样的实验。它的美妙之处在于，因为人类思维的运作方式，你可以进行NlogN并行比较(碰撞分辨率)。:-)

#24

If the "move" operation is fairly expensive, and the "compare" operation is cheap, and you need to move the whole set anyway, into a buffer where search is much faster than in original storage... just integrate sorting into the obligatory move.

如果“移动”操作相当昂贵，并且“比较”操作很便宜，那么您需要将整个集合移动到一个缓冲区中，在这个缓冲区中搜索速度要比原始存储快得多……只是把分类整理成强制性的行动。

I found integrating the process of sorting into hanging to dry makes it a breeze. I need to pick up each sock anyway, and hang it (move) and it costs me about nothing to hang it in a specific place on the strings. Now just not to force search of the whole buffer (the strings) I choose to place socks by color/shade. Darker left, brighter right, more colorful front etc. Now before I hang each sock, I look in its "right vicinity" if a matching one is there already - this limits "scan" to 2-3 other socks - and if it is, I hang the other one right next to it. Then I roll them into pairs while removing from the strings, when dry.

我发现将整理的过程与晾干的过程相结合，使它成为微风。我需要把每只袜子都捡起来，然后挂起来(移动)，在绳子上一个特定的地方把它挂起来要花很多钱。现在，我不需要强制搜索整个缓冲区(字符串)，我选择用颜色/阴影来放置袜子。在我挂袜子之前，我先看一下它的“右邻”，如果一个匹配的东西已经在那里了——这个限制“扫描”到另外2-3个袜子——如果是的话，我把另一个挂在它旁边。然后，当我把它们从绳子上取下来的时候，我把它们卷成双成对。

Now this may not seem all that different from "forming piles by color" suggested by top answers but first, by not picking discrete piles but ranges, I have no problem classifying whether "purple" goes to "red" or "blue" pile; it just goes between. And then by integrating two operations (hang to dry and sort) the overhead of sorting while hanging is like 10% of what separate sorting would be.

现在看来，这似乎与“按颜色形成桩”不同，但首先，不是选择离散的桩，而是范围，我对“紫色”到“红色”或“蓝色”堆的分类没有问题;它只是之间。然后通过集成两个操作(hang to dry和sort)，排序时的开销就相当于单独排序的10%。

#25

I hope I can contribute something new to this problem. I noticed that all of the answers neglect the fact that there are two points where you can perform preprocessing, without slowing down your overall laundry performance.

我希望我能为这个问题贡献一些新的东西。我注意到所有的答案都忽略了一个事实，即你可以在两个点上进行预处理，而不会降低整体洗衣性能。

Also, we don't need to assume a large number of socks, even for large families. Socks are taken out of the drawer and are worn, and they are tossed in a place (maybe a bin) where they stay before being laundered. While I wouldn't call said bin a LIFO-Stack, I'd say it is safe to assume that

而且，我们不需要假设大量的袜子，即使是对于大家庭。袜子从抽屉里拿出来，穿在身上，它们被扔在一个地方(也许是垃圾桶)，然后被洗干净。虽然我不会打电话给他说我是一个lifoa - stack，但我敢说这是安全的。

1. people toss both of their socks roughly in the same area of the bin,
2. 人们把两只袜子都扔在同一个地方，
3. the bin is not randomized at any point, and therefore
4. 箱子在任何时候都不是随机的，因此。
5. any subset took from the top of this bin generally contains both socks of a pair.
6. 从这个箱子的顶部取来的任何一个子集通常都包含一对袜子。

Since all washing machines I know about are limited in size (regardless of how many socks you have to wash), and the actual randomizing occurs in the washing machine, no matter how many socks we have, we always have small subsets which contain almost no singletons.

因为我所知道的所有洗衣机的尺寸都是有限的(不管你要洗多少袜子)，而且真正的随机发生在洗衣机里，不管我们有多少袜子，我们总是有一个小的子集，几乎没有一个单件。

Our two preprocessing stages are "putting the socks on the clothesline" and "Taking the socks from the clothesline", which we have to do, in order to get socks which are not only clean but also dry. As with washing machines, clotheslines are finite, and I assume that we have the whole part of the line where we put our socks in sight.

我们的两个预处理阶段是“把袜子放在晾衣绳上”和“从晾衣绳上取袜子”，这是我们必须要做的，以便得到不仅干净而且干燥的袜子。和洗衣机一样，晾衣绳也是有限的，我认为我们把袜子的全部部分都放在了看得见的地方。

Here's the algorithm for put_socks_on_line():

下面是put_socks_on_line()的算法:

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

Don't waste your time moving socks around or looking for the best match, this all should be done in O(n), which we would also need for just putting them on the line unsorted. The socks aren't paired yet, we only have several similarity clusters on the line. It's helpful that we have a limited set of socks here, as this helps us to create "good" clusters (for example, if there are only black socks in the set of socks, clustering by colours would not be the way to go)

不要把时间浪费在到处寻找或寻找最好的匹配上，这些都应该在O(n)中完成，我们也需要将它们放在未排序的线上。袜子还没有配对，我们在这条线上只有几个相似点。我们在这里有一组有限的袜子是很有帮助的，因为这可以帮助我们创建“好的”集群(例如，如果袜子里只有黑袜子，那么按颜色聚类就不是方法了)

Here's the algorithm for take_socks_from_line():

下面是take_socks_from_line()的算法:

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

I should point out that in order to improve the speed of the remaining steps, it is wise not to randomly pick the next sock, but to sequentially take sock after sock from each cluster. Both preprocessing steps don't take more time than just putting the socks on the line or in the basket, which we have to do no matter what, so this should greatly enhance the laundry performance.

我应该指出，为了提高其余步骤的速度，明智的做法是不要随机选择下一只袜子，而是从每一簇中依次取出袜子。这两个预处理步骤都不需要花费更多的时间，而不仅仅是把袜子放在绳子上或者篮子里，这是我们必须做的，所以这将大大提高洗衣的性能。

After this, it's easy to do the hash partitioning algorithm. Usually, about 75% of the socks are already paired, leaving me with a very small subset of socks, and this subset is already (somewhat) clustered (I don't introduce much entropy into my basket after the preprocessing steps). Another thing is that the remaining clusters tend to be small enough to be handled at once, so it is possible to take a whole cluster out of the basket.

在此之后，很容易做散列分区算法。通常，大约75%的袜子已经配对了，只剩下一小部分袜子，而这个子集已经(有点)聚集了(在预处理步骤之后，我不会在我的篮子里引入太多的熵)。另一件事是，剩下的集群往往很小，可以同时处理，因此可以从篮子中取出整个集群。

Here's the algorithm for sort_remaining_clusters():

下面是sort_ing_cluster()的算法:

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

After that, there are only a few socks left. This is where I introduce previously unpaired socks into the system and process the remaining socks without any special algorithm - the remaining socks are very few and can be processed visually very fast.

在那之后，只剩下几只袜子了。这是我在系统中介绍之前未配对的袜子，并在没有任何特殊算法的情况下处理剩下的袜子——剩下的袜子是非常少的，并且可以快速的处理。

For all remaining socks, I assume that their counterparts are still unwashed and put them away for the next iteration. If you register a growth of unpaired socks over time (a "sock leak"), you should check your bin - it might get randomized (do you have cats which sleep in there?)

对于所有剩余的袜子，我假定它们的副本仍然没有被清洗，并将它们放到下一次迭代中。如果你在一段时间内(“袜子泄漏”)注册了不成双的袜子，你应该检查你的箱子——它可能是随机的(你有睡在那里的猫吗?)

I know that these algorithms take a lot of assumptions: a bin which acts as some sort of LIFO stack, a limited, normal washing machine, and a limited, normal clothesline - but this still works with very large numbers of socks.

我知道这些算法需要大量的假设:一个像LIFO堆叠，一个有限的，普通的洗衣机，一个有限的，普通的晒衣绳的箱子，但是这仍然适用于大量的袜子。

About parallelism: As long as you toss both socks into the same bin, you can easily parallelize all of those steps.

关于并行性:只要把双袜子扔进同一个垃圾箱，你就可以很容易地将所有这些步骤并行化。

#26

I have taken simple steps to reduce my effort into a process taking O(1) time.

我已经采取了一些简单的步骤来减少我的工作量。

By reducing my inputs to one of two types of socks (white socks for recreation, black socks for work), I only need to determine which of two socks I have in hand. (Technically, since they are never washed together, I have reduced the process to O(0) time)

通过将我的输入减少到两种袜子中的一种(白袜子用于娱乐，黑色袜子用于工作)，我只需要确定我手中的两只袜子中的哪一个。(从技术上讲，因为它们从来没有一起洗过，所以我把这个过程缩短到了O(0)时间)

Some upfront effort is required to find desirable socks, and to purchase in sufficient quantity as to eliminate need for your existing socks. As I'd done this before my need for black socks, my effort was minimal, but mileage may vary.

需要一些前期的努力才能找到合适的袜子，并购买足够数量的袜子来消除你现有袜子的需求。就像我在需要黑袜子之前做的那样，我的努力是最小的，但是里程可能会有所不同。

Such an upfront effort has been seen many times in very popular and effective code. Examples include #DEFINE'ing pi to several decimals (other examples exist, but that's the one that comes to mind right now).

这种预先的努力在非常流行和有效的代码中已经见过很多次了。示例包括#DEFINE'ing pi到几个小数(其他的例子存在，但这是现在想到的)。

#27

Create a hash table which will be used for unmatched socks, using the pattern as the hash. Iterate over the socks one by one. If the sock has a pattern match in the hash table, take the sock out of the table and make a pair. If the sock does not have a match, put it into the table.

创建一个散列表，该列表将用于不匹配的socks，使用模式作为散列。一个接一个地重复穿袜子。如果袜子在哈希表中有一个模式匹配，就把袜子从桌子上拿出来，做一对。如果袜子没有火柴，就把它放在桌子上。

#28

The problem of sorting your n pairs of socks is O(n). Before you throw them in the laundry basket, you thread the left one to the right one. On taking them out, you cut the thread and put each pair into your drawer - 2 operations on n pairs, so O(n).

n对袜子的分类问题是O(n)。在你把它们扔进洗衣篮里之前，你把左边的那个给了右边的那个。把它们拿出来，你就把线剪下来，把每一对放到抽屉里- 2个操作在n对上，所以O(n)

Now the next question is simply whether you do your own laundry and your wife does hers. That is a problem likely in an entirely different domain of problems. :)

现在的问题是，你是否自己洗衣服，你的妻子也会洗衣服。这可能是一个完全不同领域的问题。:)

#29

I've finished pairing my socks just right now, and I found that the best way to do it is the following:

我现在已经完成了袜子的配对，我发现最好的方法是:

• Choose one of the socks and put it away (create a 'bucket' for that pair)
• 选择一只袜子并把它收起来(为这双袜子创建一个“桶”)
• If the next one is the pair of the previous one, then put it to the existing bucket, otherwise create a new one.
• 如果下一个是前一个，那么将它放到现有的bucket中，否则创建一个新的bucket。

In the worst case it means that you will have n/2 different buckets, and you will have n-2 determinations about that which bucket contains the pair of the current sock. Obviously, this algorithm works well if you have just a few pairs; I did it with 12 pairs.

在最坏的情况下，这意味着你将有n/2个不同的桶，而你将有n-2个决定，关于哪个桶包含了现在的袜子。显然，如果你只有几对，这个算法就会很有效;我做了12对。

It is not so scientific, but it works well:)

这不是很科学，但效果很好:)

#30

What about doing some preprocessing? I would stitch a mark or id number in every sock in a way that every pair has the same mark/id number. This process might be done every time you buy a new pair of socks. Then, you could do a radix sort to get O(n) total cost. Find a place for every mark/id number and just pick all the socks one by one and put them into the correct place.

做一些预处理怎么样?我将在每只袜子上缝上一个标记或id号，每一对都有相同的标记/id号。这个过程可能会在每次你买一双新袜子的时候完成。然后，你可以做一个基数排序来得到O(n)的总成本。为每一个标记/身份证号码找一个地方，然后把所有的袜子一个一个地拣起来放在正确的地方。