昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
理论上的限制是O（n），因为你需要触摸每一只袜子（除非有些袜子已经配对）。
你可以用基数排序实现O（n）。你只需要为桶选择一些属性。
首先你可以选择（她的，我的）-把它们分成两堆，然后使用颜色（可以有任何颜色的顺序，例如按颜色名称的字母顺序）-按颜色将它们分成一堆（记住对同一堆中的所有袜子保持步骤1中的初始顺序），然后袜子的长度，然后是纹理，....
如果您可以选择有限数量的属性，但有足够多的属性可以唯一地标识每对属性，则应该使用O（k*n），如果我们可以考虑k是有限的，则使用O（n）。
其他回答
考虑大小为“N”的哈希表。
如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）
我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章
让“N”对应于袜子独特颜色/图案数量的近似上限。
一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）
我的解决方案并不完全符合您的要求，因为它正式需要O（n）“额外”空间。然而，考虑到我的条件，它在我的实际应用中非常有效。因此，我认为这应该很有趣。
与其他任务合并
我的特殊情况是，我不用烘干机，只是把衣服挂在普通的烘干机上。挂布需要O（n）操作（顺便说一句，我在这里总是考虑垃圾箱包装问题），这个问题本质上需要线性的“额外”空间。当我从桶里拿出一只新袜子时，如果这双袜子已经挂好了，我会试着把它挂在旁边。如果是新袜子，我会在旁边留出一些空间。
Oracle机器更好；-）
显然，这需要一些额外的工作来检查是否有匹配的袜子已经挂在某个地方，这将为计算机提供系数约为1/2的解O（n^2）。但在这种情况下，“人为因素”实际上是一种优势——如果匹配的袜子已经挂起，我通常可以很快（几乎为O（1））识别出它（可能涉及到大脑缓存中的一些难以察觉的因素）——将其视为一种有限的“预言机”，如oracle Machine；-）我们人类在某些情况下比数字机器有这些优势；-）
快到O（n）！
因此，将袜子配对的问题与挂布的问题联系起来，我可以免费获得O（n）“额外的空间”，并有一个及时的解决方案，大约O（n），只需要比简单的挂布多一点的工作，即使在非常糟糕的星期一早晨，也可以立即获得一双完整的袜子…；-）
做一些预处理怎么样？我会在每只袜子上缝上一个标记或身份证号码，这样每双袜子都有相同的标记/身份证号码。这个过程可能在你每次买一双新袜子时都会完成。然后，您可以进行基数排序以获得O（n）总成本。为每个标记/身份证号码找一个位置，只需逐一挑选所有袜子并将它们放在正确的位置。
排序解决方案已经提出，但排序有点太多了：我们不需要排序；我们只需要平等团体。
所以散列就足够了（而且更快）。
对于每种颜色的袜子，形成一堆。重复输入篮中的所有袜子，并将它们分配到颜色堆上。在每个桩上循环，并通过其他度量（例如模式）将其分配到第二组桩中递归地应用此方案，直到您将所有袜子分发到非常小的堆上，您可以立即进行可视化处理
当SQL Server需要对庞大的数据集进行哈希连接或哈希聚合时，这种递归哈希分区实际上是由它完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个CPU。
如果您可以找到一个分发密钥（哈希密钥），该密钥提供足够的存储桶，使得每个存储桶足够小，可以快速处理，那么您就不需要递归分区。不幸的是，我认为袜子没有这种特性。
如果每只袜子都有一个名为“PairID”的整数，那么可以根据PairID%10（最后一位）轻松地将它们分配到10个桶中。
我能想到的现实世界中最好的分区是创建一个堆积的矩形：一个维度是颜色，另一个是图案。为什么是长方形？因为我们需要O（1）随机访问桩。（3D长方体也可以，但这不太实用。）
更新：
并行性呢？多人能更快地匹配袜子吗？
最简单的并行化策略是让多个工人从输入篮中取出袜子，然后将袜子放到堆上。这只会增加这么多——想象100人在10个桩上战斗。同步成本（表现为手部碰撞和人类通信）破坏了效率和加速（参见通用可扩展性定律！）。这是否容易陷入僵局？不，因为每个工人一次只需要访问一堆。只有一个“锁”，就不会出现死锁。活锁可能是可能的，这取决于人类如何协调对桩的访问。他们可能只是使用随机退避，就像网卡在物理级别上那样，以确定什么卡可以独占地访问网络线路。如果它适用于NIC，那么它也应该适用于人类。如果每个工人都有自己的一组桩，它几乎可以无限扩展。然后，工人可以从输入篮中取出大块袜子（很少有人争抢，因为他们很少这样做），而且他们在分发袜子时根本不需要同步（因为他们有线程局部堆）。最后，所有工人都需要联合他们的桩组。我相信，如果工人形成一个聚合树，这可以在O（log（工人计数*每个工人的桩数））中完成。
元素的清晰度问题呢？正如文章所述，元素区别问题可以用O（N）来解决。袜子问题也是如此（如果你只需要一个分发步骤（我提出了多个步骤，只是因为人类不擅长计算-如果你在md5上分发（颜色、长度、图案…），即所有属性的完美哈希），那么一个步骤就够了）。
显然，一个速度不能比O（N）快，所以我们已经达到了最佳下限。
虽然输出不完全相同（在一种情况下，只是布尔值。在另一种情况中，是袜子对），但渐近复杂性是相同的。
我提出的解决方案假设所有袜子在细节上都是相同的，除了颜色。如果袜子之间有更多的细节需要延迟，这些细节可以用来定义不同类型的袜子，而不是我的例子中的颜色。。
假设我们有一堆袜子，袜子可以有三种颜色：蓝色、红色或绿色。
然后，我们可以为每种颜色创建一个并行工作程序；它有自己的列表来填充相应的颜色。
At time i:
Blue read Pile[i] : If Blue then Blue.Count++ ; B=TRUE ; sync
Red read Pile[i+1] : If Red then Red.Count++ ; R=TRUE ; sync
Green read Pile [i+2] : If Green then Green.Count++ ; G=TRUE ; sync
同步过程：
Sync i:
i++
If R is TRUE:
i++
If G is TRUE:
i++
这需要初始化：
Init:
If Pile[0] != Blue:
If Pile[0] = Red : Red.Count++
Else if Pile[0] = Green : Green.Count++
If Pile[1] != Red:
If Pile[0] = Green : Green.Count++
哪里
Best Case: B, R, G, B, R, G, .., B, R, G
Worst Case: B, B, B, .., B
Time(Worst-Case) = C * n ~ O(n)
Time(Best-Case) = C * (n/k) ~ O(n/k)
n: number of sock pairs
k: number of colors
C: sync overhead
