如何高效地从一堆袜子中匹配成对？

当我整理袜子时，我会使用近似的基数排序方法，将颜色/图案相同的袜子放在附近。除非我能够看到一个与即将放置袜子完全匹配的袜子，否则我会在那个位置提取成对的袜子。

几乎所有其他算法（包括usr提供的最高得分答案）都是先排序，然后再删除成对的袜子。但是，作为人类，我发现最好尽量减少一次考虑的袜子数量。

我通过以下方式实现：

1. 挑选一个独特的袜子（在堆中首先引起我的注意）。
2. 从该概念位置开始进行基数排序，根据与该袜子的相似性从堆中取出袜子。
3. 将新袜子靠近当前堆放置，距离根据其不同程度而定。如果您发现自己因为两只袜子完全相同而将一只袜子放在另一只上面，请在那里形成一对并将它们移除。这意味着未来的比较需要更少的努力才能找到正确的位置。

这利用了人类模糊匹配的能力，在O(1)时间内完成，有点类似于在计算设备上建立哈希映射。
通过先挑选出特别的袜子，你可以留出空间来“放大”最初不那么明显的特征。
在淘汰荧光色、条纹袜和三双长袜后，你可能会剩下大部分按磨损程度粗略分类的白袜子。
在某个时候，袜子之间的差异足够小，以至于其他人不会注意到差异，进一步匹配也是不必要的。

每当你拿起一只袜子，就把它放在同一个地方。然后下一只袜子，如果与第一只不匹配，就把它放在第一只旁边。如果匹配，那就是一双。这样，无论有多少组合，都没有关系，每次拿起的袜子只有两种可能性——它已经有与之匹配的袜子在数组中，或者没有，这意味着你要将它添加到数组中的某个位置。

这也意味着你几乎肯定永远不会有所有的袜子都在数组中，因为随着它们被匹配，它们会被移除。

考虑一个大小为'N'的哈希表。
如果我们假设正态分布，则至少有一个袜子映射到一个桶中的估计插入次数为NlogN（即，所有桶都已满）。
我曾将此作为另一个难题的一部分推导出来，但很高兴被证明是错误的。 这是我关于同样问题的博客文章 让'N'对应于你拥有的唯一颜色/袜子图案数量的近似上限。
一旦发生冲突（也称为匹配），只需移除该对袜子。然后使用下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，您可以进行NlogN个并行比较（冲突解决）。 :-)

无论是真正的袜子还是类似的数据结构，都应该成对提供。最简单的答案是在允许分离一对袜子之前，应该初始化一个包含左右袜子指针的单个数据结构，从而使得可以直接或通过它们的配对引用袜子。袜子也可以扩展到包含指向其伴侣的指针。这通过一层抽象解决了任何计算上的配对问题。
将相同的想法应用于配对袜子的实际问题时，显而易见的答案是：永远不要让你的袜子失配。袜子成对提供，成对放在抽屉里（或许将它们捏成一团），成对穿着。但是可能出现的失配情况是在洗衣机里，因此需要一种物理机制来使袜子保持在一起并且能够高效地洗涤。
有两种物理可能性： 对于一个“配对”对象，它保留每只袜子的指针，我们可以使用布袋来将袜子绑在一起。这似乎是巨大的开销。 但为了确保每只袜子都有对另一只的引用，有一个巧妙的解决方案：一种按扣（如果你是美国人，则是“snap button”），如下所示： http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html 然后，你只需在脱下袜子后将它们捏在一起，并将它们放入洗衣篮中，你就解决了需要使用“配对”概念的物理抽象来配对袜子的问题。

我希望我能对这个问题做出一些新的贡献。我注意到所有答案都忽略了一个事实，即有两个可以进行预处理的点，而不会降低您整体洗涤效率。

此外，即使对于大家庭，我们也不需要假设有大量的袜子。袜子被拿出抽屉穿着，然后扔到一个地方（可能是一个箱子）等待洗涤。虽然我不会称之为LIFO-堆栈，但我可以说可以安全地假设：

1. 人们将两只袜子粗略地扔在箱子的同一区域，
2. 箱子在任何时候都不会随机排列，因此
3. 从该箱子顶部取出的任何子集通常都包含一对袜子。

由于我所知道的所有洗衣机都有尺寸限制（无论要洗多少只袜子），而实际的随机过程发生在洗衣机中，因此，无论我们有多少只袜子，我们总会有包含几乎没有单一项的小子集。

我们的两个预处理阶段是“把袜子挂在晾衣绳上”和“从晾衣绳上取下袜子”，为了得到既干净又干燥的袜子，我们必须这样做。与洗衣机一样，晾衣绳也是有限的，我假设我们可以看到放袜子的整个部分。

以下是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 
 }
}

不要浪费时间来移动袜子或寻找最佳搭配，这一切都应该在O(n)的时间内完成，这也适用于未排序的放置。

这些袜子尚未成对，我们只有线上的几个相似聚类。很幸运的是，我们这里只有有限的袜子集，这有助于我们创建“好”的聚类（例如，如果袜子集中只有黑色袜子，则按颜色聚类不是正确的方法）

以下是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
 }

我需要指出的是，为了提高剩余步骤的速度，明智的做法不是随意选择下一只袜子，而是依次从每个簇中取出袜子。这两个预处理步骤所需的时间不比将袜子放在线上或篮子里更长，而我们无论如何都必须这样做，因此这应该大大提高洗衣效率。

之后，执行哈希分区算法就很容易了。通常，约有75%的袜子已经成对，留下的袜子非常少，而且这个子集已经（有点）聚类（在预处理步骤后，我在篮子里没有引入太多熵）。另外一件事是，剩余的簇往往足够小，可以一次性处理完，因此可以将整个簇从篮子中取出。

以下是sort_remaining_clusters()算法：

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

然后，只剩下几只袜子了。这时我会将之前未成对的袜子引入系统，处理剩余的袜子时不需要任何特殊算法 - 剩余的袜子很少，可以通过视觉快速处理。

对于所有剩余的袜子，我假设它们的配对袜仍未清洗干净，并将它们放在一旁等待下一轮迭代。如果你发现未成对袜子数量逐渐增加（"袜子泄漏"），你应该检查你的垃圾桶 - 它可能已经被打乱了（你有没有睡在那里的猫？）

我知道这些算法基于许多假设：一个像LIFO堆栈的垃圾桶，一个有限的普通洗衣机和普通的晾衣绳 - 但即使在大量的袜子情况下，这个方法仍然有效。

关于并行性： 只要把两只袜子扔进同一个垃圾桶里，你就可以轻松地并行化所有这些步骤。

如果“移动”操作非常昂贵，而“比较”操作很便宜，并且您需要将整个集合移动到一个缓冲区中，在该缓冲区中搜索比在原始存储中快得多…只需将排序集成到强制移动中即可。
我发现将干燥过程中的排序过程整合起来非常容易。我需要捡起每只袜子，然后挂起它（移动），将其挂在绳子上的特定位置几乎不花费任何代价。现在只需不强制搜索整个缓冲区（字符串），我选择按颜色/阴影放置袜子。越暗左边，越亮右边，更多的颜色在前面等等。现在，在我挂每只袜子之前，我会在其“正确附近”查找是否已经有匹配的袜子-这将限制“扫描”的范围为2-3只其他袜子-如果有，则将另一只挂在其旁边。然后，当它们干燥时，我将它们卷成一对对从绳子上取下来。
现在，这可能与顶部答案建议的“按颜色形成堆”并没有太大的不同，但首先，通过不选择离散堆而是选择范围，我没有问题将“紫色”归类为“红色”或“蓝色”堆；它只是在中间。然后通过整合两个操作（挂起干燥和排序），挂起时的排序开销就像单独排序的10％。

创建一个哈希表，用于存放未匹配的袜子，使用图案作为哈希。逐个迭代袜子。如果袜子在哈希表中有图案匹配，则从表中取出袜子并成对。如果袜子没有匹配，则将其放入表中。

我刚刚完成了袜子的搭配，发现最好的方法是这样的：

• 选择其中一只袜子并放到一边（为那对袜子创建一个“桶”）
• 如果下一只袜子是前一只袜子的一对，则将其放入现有的“桶”中，否则创建一个新的“桶”。

在最坏的情况下，你会有n/2个不同的“桶”，并且你将得出n-2个关于当前袜子属于哪个“桶”的决定。显然，如��你只有几双袜子，这个算法很有效；我用它来处理12双袜子。

虽然这不太科学，但它效果很好 :)

你需要为你的n双袜子进行排序，这个问题的时间复杂度是O(n)。在把它们扔进洗衣篮之前，你要把左边的袜子穿到右边的袜子上。拿出来后，你要剪断线头，把每对袜子放到抽屉里——对n双袜子进行了2次操作，因此时间复杂度为O(n)。
现在的问题是你是否自己洗衣服，而你的妻子则洗她自己的衣服。这是一个完全不同领域的问题。 :)

我的解决方案并不完全符合您的要求，因为它正式要求“额外”的O(n)空间。然而，考虑到我的条件，在我的实际应用中非常高效。因此我认为这应该很有趣。
与其他任务结合
在我的情况下，特殊条件是我不使用烘干机，只是把衣服挂在普通的晾衣架上。挂衣服需要O(n)操作（顺便说一句，我总是在这里考虑bin packing问题），由于本质上的问题需要线性的“额外”空间。当我从桶里拿出一只新袜子时，我会尝试将其挂在旁边，如果它的配对已经挂了。如果它是一双新袜子，我会在它旁边留出一些空间。
Oracle机器更好 ;-)
显然，检查是否已经有匹配的袜子挂在某个地方需要一些额外的工作，并且会使计算机的解决方案 O(n^2) 的系数为 1/2。但在这种情况下，“人的因素”实际上是一个优势——如果已经挂了匹配的袜子，我通常可以非常快速地（几乎 O(1)）识别出匹配的袜子（可能涉及一些无法察觉的脑内缓存），可以将其视为一种有限的“Oracle”，就像 Oracle Machine 一样；-) 在某些情况下，我们人类在数字机器方面具有这些优势 ;-)
因此，将袜子配对问题与悬挂衣服问题联系起来，我免费获得了 O(n) 的“额外空间”，并且拥有一个大约 O(n) 时间的解决方案，比简单的悬挂衣服需要更少的工作，并允许立即访问完整的袜子对，即使在非常糟糕的星期一早上...;-)