昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
创建一个哈希表，该表将用于不匹配的袜子，使用模式作为哈希。一只一只地重复袜子。如果袜子在哈希表中有图案匹配，请将袜子从表中取出并配对。如果袜子没有火柴，就把它放到桌子上。
其他回答
成本：移动袜子->高，查找/搜索袜子排成一排->小
我们想做的是减少移动次数，并用搜索次数进行补偿。此外，我们还可以利用智人的多威胁环境，在解密缓存中保存更多的东西。
X=您的，Y=您的配偶
从所有袜子的A堆开始：
选择两个袜子，将相应的X袜子放在X线上，将Y袜子放在Y线上的下一个可用位置。
直到A为空。
对于每行X和Y
选择行中的第一只袜子，沿着行搜索，直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时，当前正在查看的袜子与之前的袜子相同，请对这些袜子执行步骤2。
可选地，在第一步中，您从该行中拾取两个袜子，而不是两个，因为缓存内存足够大，我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，那么考虑到受试者的记忆足够大，你可以同时解析三只袜子。
直到X和Y都为空。
Done
然而，由于这与选择排序具有相似的复杂性，由于I/O（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。
我的解决方案并不完全符合您的要求，因为它正式需要O（n）“额外”空间。然而，考虑到我的条件，它在我的实际应用中非常有效。因此，我认为这应该很有趣。
与其他任务合并
我的特殊情况是，我不用烘干机，只是把衣服挂在普通的烘干机上。挂布需要O（n）操作（顺便说一句，我在这里总是考虑垃圾箱包装问题），这个问题本质上需要线性的“额外”空间。当我从桶里拿出一只新袜子时，如果这双袜子已经挂好了，我会试着把它挂在旁边。如果是新袜子，我会在旁边留出一些空间。
Oracle机器更好；-）
显然，这需要一些额外的工作来检查是否有匹配的袜子已经挂在某个地方，这将为计算机提供系数约为1/2的解O（n^2）。但在这种情况下，“人为因素”实际上是一种优势——如果匹配的袜子已经挂起，我通常可以很快（几乎为O（1））识别出它（可能涉及到大脑缓存中的一些难以察觉的因素）——将其视为一种有限的“预言机”，如oracle Machine；-）我们人类在某些情况下比数字机器有这些优势；-）
快到O（n）！
因此，将袜子配对的问题与挂布的问题联系起来，我可以免费获得O（n）“额外的空间”，并有一个及时的解决方案，大约O（n），只需要比简单的挂布多一点的工作，即使在非常糟糕的星期一早晨，也可以立即获得一双完整的袜子…；-）
每当你拿起袜子时，把它放在一个地方。然后你拿起的下一只袜子，如果它与第一只袜子不匹配，就把它放在第一只袜子旁边。如果是，那就有一对。这样，有多少种组合其实并不重要，而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配，要么它没有匹配，这意味着你将它添加到数组中的一个位置。
这也意味着你几乎肯定不会把所有袜子都放在阵列中，因为袜子会在搭配时被取下。
当我对袜子进行排序时，我会进行近似基数排序，将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近，我能看到一对完全匹配的袜子，否则我会在那一刻取出这双袜子。
几乎所有其他算法（包括usr评分最高的答案）排序，然后删除配对。我发现，作为一个人，一次考虑的袜子数量最好尽量减少。
我通过以下方式做到这一点：
挑选一只与众不同的袜子（在袜子堆里最先映入我眼帘的东西）。从概念位置开始基数排序，根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近，距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面，因为它是相同的，请在那里形成一对，然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。
这利用了人类在O（1）时间内进行模糊匹配的能力，这在某种程度上相当于在计算设备上建立哈希图。
通过先穿上与众不同的袜子，你可以留出空间来“放大”那些不那么与众不同的特征。
在去除了浅色、条纹袜子和三双长袜之后，你可能最终会得到大致按磨损程度分类的白色袜子。
在某种程度上，袜子之间的差异很小，以至于其他人不会注意到差异，因此不需要进一步的匹配。
真实世界方法：
尽快将袜子从未分类的袜子堆中取出，一次一个，然后放在前面。桩应布置得有一定的空间效率，所有袜子指向相同的方向；桩的数量受你容易到达的距离的限制。选择一堆袜子时，应尽快将袜子放在一堆看起来很像的袜子上；偶尔出现的I型（把袜子放在不属于它的袜子堆上）或II型（当有一堆类似的袜子时，把袜子放进自己的袜子堆里）错误是可以容忍的——最重要的考虑是速度。
一旦所有袜子都成了一堆，快速穿过多个袜子堆，创建成对的袜子，然后将它们取下（这些袜子朝抽屉方向）。如果袜子堆中有不匹配的袜子，请将它们重新堆到最好的位置（在尽可能快的限制范围内）。当处理完所有的多袜子堆后，将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦，你完了——我有很多袜子，直到大部分都脏了才洗。另一个实际注意事项是：我将一双袜子的顶部翻转到另一双袜子上，利用它们的弹性财产，以便它们在被运送到抽屉和抽屉中时保持在一起。
