昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
对于p双袜子（n=2p只袜子），我实际上是这样做的：
从袜子堆里随便拿一只袜子。对于第一只袜子，或者如果之前选择的所有袜子都已配对，只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子，请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时，可以将袜子分为普通类别或类型（白色/黑色、脚踝/圆领、运动型/连衣裙），并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配，把两只袜子放在一起，然后把它们从阵列中去掉。如果没有，请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。
这种方案的最坏情况是，每双袜子都不同，必须完全匹配，而且你挑选的第一双n/2袜子都不同。这是你的O（n2）场景，极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2，并且每种类型的袜子都足够相似（通常在穿着相关的术语中），使得该类型的任何袜子都可以与任何其他袜子配对，那么正如我上面所推断的，你必须与之进行比较的袜子的最大数量是t，之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生，并将最坏情况的复杂性降低到O（n*t），其中通常t<<n。
其他回答
排序解决方案已经提出，但排序有点太多了：我们不需要排序；我们只需要平等团体。
所以散列就足够了（而且更快）。
对于每种颜色的袜子，形成一堆。重复输入篮中的所有袜子，并将它们分配到颜色堆上。在每个桩上循环，并通过其他度量（例如模式）将其分配到第二组桩中递归地应用此方案，直到您将所有袜子分发到非常小的堆上，您可以立即进行可视化处理
当SQL Server需要对庞大的数据集进行哈希连接或哈希聚合时，这种递归哈希分区实际上是由它完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个CPU。
如果您可以找到一个分发密钥（哈希密钥），该密钥提供足够的存储桶，使得每个存储桶足够小，可以快速处理，那么您就不需要递归分区。不幸的是，我认为袜子没有这种特性。
如果每只袜子都有一个名为“PairID”的整数，那么可以根据PairID%10（最后一位）轻松地将它们分配到10个桶中。
我能想到的现实世界中最好的分区是创建一个堆积的矩形：一个维度是颜色，另一个是图案。为什么是长方形？因为我们需要O（1）随机访问桩。（3D长方体也可以，但这不太实用。）
更新：
并行性呢？多人能更快地匹配袜子吗？
最简单的并行化策略是让多个工人从输入篮中取出袜子，然后将袜子放到堆上。这只会增加这么多——想象100人在10个桩上战斗。同步成本（表现为手部碰撞和人类通信）破坏了效率和加速（参见通用可扩展性定律！）。这是否容易陷入僵局？不，因为每个工人一次只需要访问一堆。只有一个“锁”，就不会出现死锁。活锁可能是可能的，这取决于人类如何协调对桩的访问。他们可能只是使用随机退避，就像网卡在物理级别上那样，以确定什么卡可以独占地访问网络线路。如果它适用于NIC，那么它也应该适用于人类。如果每个工人都有自己的一组桩，它几乎可以无限扩展。然后，工人可以从输入篮中取出大块袜子（很少有人争抢，因为他们很少这样做），而且他们在分发袜子时根本不需要同步（因为他们有线程局部堆）。最后，所有工人都需要联合他们的桩组。我相信，如果工人形成一个聚合树，这可以在O（log（工人计数*每个工人的桩数））中完成。
元素的清晰度问题呢？正如文章所述，元素区别问题可以用O（N）来解决。袜子问题也是如此（如果你只需要一个分发步骤（我提出了多个步骤，只是因为人类不擅长计算-如果你在md5上分发（颜色、长度、图案…），即所有属性的完美哈希），那么一个步骤就够了）。
显然，一个速度不能比O（N）快，所以我们已经达到了最佳下限。
虽然输出不完全相同（在一种情况下，只是布尔值。在另一种情况中，是袜子对），但渐近复杂性是相同的。
考虑大小为“N”的哈希表。
如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）
我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章
让“N”对应于袜子独特颜色/图案数量的近似上限。
一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）
由于人脑的结构与现代CPU完全不同，所以这个问题毫无实际意义。
人类可以利用“找到匹配的对”这一事实来战胜CPU算法，这对于一个不太大的集合来说是一个操作。
我的算法：
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);
}
至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但通常很丰富。
Defant&Kravitz（1）给出了一种算法，通过将袜子依次放在脚上和脚下来对袜子进行排序。
他们的算法适用于任意数量的英尺。
本文给出了（定理1.1）可使用单脚排序的袜子订单的特征。从他们的定理1.3可以看出，每一个4种颜色的袜子订单最多可以用两只脚进行排序，而有5种颜色的袜订单不可能用两只脚排序。
Colin Defant和Noah Kravitz，袜子足部分类（2022）
拿起第一只袜子放在桌子上。现在再挑一只袜子；如果它与第一个拾取的匹配，请将其放在第一个拾取上。如果没有，把它放在桌子上，离第一个小距离。挑选第三只袜子；如果它与前两个匹配，请将它放在它们的上面，或者将它放置在距离第三个的一小段距离处。重复上述步骤，直到你捡起所有袜子。
