昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在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。
其他回答
考虑大小为“N”的哈希表。
如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）
我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章
让“N”对应于袜子独特颜色/图案数量的近似上限。
一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）
我刚刚完成袜子配对，我发现最好的方法是：
选择一只袜子并将其收起来（为这双袜子创建一个“水桶”）如果下一个是上一个的一对，则将其放到现有的存储桶中，否则创建一个新的存储桶。
在最坏的情况下，这意味着您将有n/2个不同的存储桶，并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然，如果你只有几对，这个算法会很好地工作；我用了12双鞋。
它不是那么科学，但它工作得很好：）
非算法答案，但当我这样做时“高效”：
步骤1）丢弃所有现有袜子第2步）去沃尔玛买10-n包的白色和m包黑色。日常无需其他颜色生活
然而，有时，我不得不再次这样做（丢失的袜子、损坏的袜子等），我讨厌太频繁地丢弃完美的袜子（我希望他们继续出售相同的袜子参考！），所以我最近采取了不同的方法。
算法答案：
考虑一下，如果你只为第二叠袜子画一只袜子，就像你正在做的那样，你在天真的搜索中找到匹配袜子的几率很低。
所以，随机挑选其中五个，记住它们的形状或长度。
为什么是五？通常情况下，人类在工作记忆中记住五到七个不同的元素是很好的——有点像RPN堆栈的人类等价物——五个是安全的默认值。
从2n-5的堆栈中选择一个。现在，在你画的五个图案中寻找一个匹配（视觉模式匹配-人类擅长用一个小堆栈），如果你没有找到一个，那么把它添加到你的五个。继续从袜子堆中随机挑选袜子，并与你的5+1袜子进行比较。随着堆栈的增长，它会降低性能，但会提高赔率。快得多。
请随意写下公式，以计算50%的匹配几率需要抽取多少样本。IIRC这是一个超几何定律。
我每天早上都会这样做，很少需要三次以上的平局——但我有n双类似的m形白袜子（大约10双，不分输赢）。现在你可以估计我的股票堆的大小：-）
顺便说一句，我发现，每次我需要一双袜子时，整理所有袜子的交易成本之和远远少于一次整理和装订袜子。准时制的效果更好，因为这样你就不必绑袜子了，而且边际回报也在减少（也就是说，当你在洗衣店的某个地方时，你一直在寻找那两到三只袜子，而你需要完成袜子的搭配，而你却在这上面浪费了时间）。
我的解决方案并不完全符合您的要求，因为它正式需要O（n）“额外”空间。然而，考虑到我的条件，它在我的实际应用中非常有效。因此，我认为这应该很有趣。
与其他任务合并
我的特殊情况是，我不用烘干机，只是把衣服挂在普通的烘干机上。挂布需要O（n）操作（顺便说一句，我在这里总是考虑垃圾箱包装问题），这个问题本质上需要线性的“额外”空间。当我从桶里拿出一只新袜子时，如果这双袜子已经挂好了，我会试着把它挂在旁边。如果是新袜子，我会在旁边留出一些空间。
Oracle机器更好；-）
显然，这需要一些额外的工作来检查是否有匹配的袜子已经挂在某个地方，这将为计算机提供系数约为1/2的解O（n^2）。但在这种情况下，“人为因素”实际上是一种优势——如果匹配的袜子已经挂起，我通常可以很快（几乎为O（1））识别出它（可能涉及到大脑缓存中的一些难以察觉的因素）——将其视为一种有限的“预言机”，如oracle Machine；-）我们人类在某些情况下比数字机器有这些优势；-）
快到O（n）！
因此，将袜子配对的问题与挂布的问题联系起来，我可以免费获得O（n）“额外的空间”，并有一个及时的解决方案，大约O（n），只需要比简单的挂布多一点的工作，即使在非常糟糕的星期一早晨，也可以立即获得一双完整的袜子…；-）
Defant&Kravitz（1）给出了一种算法，通过将袜子依次放在脚上和脚下来对袜子进行排序。
他们的算法适用于任意数量的英尺。
本文给出了（定理1.1）可使用单脚排序的袜子订单的特征。从他们的定理1.3可以看出，每一个4种颜色的袜子订单最多可以用两只脚进行排序，而有5种颜色的袜订单不可能用两只脚排序。
Colin Defant和Noah Kravitz，袜子足部分类（2022）
