昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
我提出了另一个解决方案，它不会承诺更少的操作，也不会减少时间消耗，但应该尝试看看它是否能成为一个足够好的启发式方法，在大量袜子配对中提供更少的时间消耗。
前提条件：不能保证有相同的袜子。如果它们的颜色相同，并不意味着它们的大小或图案相同。袜子随机洗牌。袜子的数量可能是奇数（有些不见了，我们不知道有多少）。准备记住一个变量“index”并将其设置为0。
结果将有一个或两个桩：1。“匹配”和2。“缺少”
启发式：
找到最与众不同的袜子。找到匹配项。如果没有匹配项，请将其放在“缺失”堆上。从1开始重复。直到没有最与众不同的袜子。如果袜子少于6只，请转到11只。盲目地将所有袜子与邻居配对（不要打包）找到所有匹配的对，将其打包并将打包的对移动到“匹配”的堆中；如果没有新的匹配项-将“索引”增加1如果“index”大于2（这可能取决于袜子的值因为袜子数量越多盲目配对）进入11打乱其余的转到1忘记“索引”挑选一只袜子查找其配对如果没有袜子，就把它移到“失踪”的那一堆如果找到匹配项，将其配对，将其打包并移动到“匹配”堆中如果还有不止一只袜子，那就去12只如果只剩下一个，请转到14满意的微笑：）
此外，还可以添加检查袜子是否损坏，就像移除袜子一样。它可以插入2到3之间，13到14之间。
我期待听到任何经验或更正。
其他回答
Defant&Kravitz（1）给出了一种算法，通过将袜子依次放在脚上和脚下来对袜子进行排序。
他们的算法适用于任意数量的英尺。
本文给出了（定理1.1）可使用单脚排序的袜子订单的特征。从他们的定理1.3可以看出，每一个4种颜色的袜子订单最多可以用两只脚进行排序，而有5种颜色的袜订单不可能用两只脚排序。
Colin Defant和Noah Kravitz，袜子足部分类（2022）
袜子，无论是真的还是类似的数据结构，都将成对提供。
最简单的答案是，在允许袜子对分开之前，应该初始化袜子对的单个数据结构，该结构包含指向左右袜子的指针，从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。
这通过使用抽象层来消除任何计算配对问题。
将同样的想法应用于袜子配对的实际问题，显而易见的答案是：不要让你的袜子不配对。袜子是一双提供的，一双放在抽屉里（也许是把它们捆在一起），一双穿。但可能脱漆的地方是在洗衣机里，所以所需要的只是一个物理机制，让袜子保持在一起并有效地清洗。
有两种物理可能性：
对于一个“pair”对象，它保持指向每只袜子的指针，我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。
但是，为了让每一只袜子都能互相参照，有一个很好的解决方案：一个popper（如果你是美国人，可以使用“按扣”），比如：
http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html
然后，你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起，再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。
每当你拿起袜子时，把它放在一个地方。然后你拿起的下一只袜子，如果它与第一只袜子不匹配，就把它放在第一只袜子旁边。如果是，那就有一对。这样，有多少种组合其实并不重要，而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配，要么它没有匹配，这意味着你将它添加到数组中的一个位置。
这也意味着你几乎肯定不会把所有袜子都放在阵列中，因为袜子会在搭配时被取下。
成本：移动袜子->高，查找/搜索袜子排成一排->小
我们想做的是减少移动次数，并用搜索次数进行补偿。此外，我们还可以利用智人的多威胁环境，在解密缓存中保存更多的东西。
X=您的，Y=您的配偶
从所有袜子的A堆开始：
选择两个袜子，将相应的X袜子放在X线上，将Y袜子放在Y线上的下一个可用位置。
直到A为空。
对于每行X和Y
选择行中的第一只袜子，沿着行搜索，直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时，当前正在查看的袜子与之前的袜子相同，请对这些袜子执行步骤2。
可选地，在第一步中，您从该行中拾取两个袜子，而不是两个，因为缓存内存足够大，我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，那么考虑到受试者的记忆足够大，你可以同时解析三只袜子。
直到X和Y都为空。
Done
然而，由于这与选择排序具有相似的复杂性，由于I/O（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。
这是问错了问题。正确的问题是，我为什么要花时间整理袜子？如果你选择X个货币单位来计算你的空闲时间，那么每年的花费是多少？
通常情况下，这不仅仅是任何空闲时间，这是早晨的空闲时间，你可以躺在床上，或者喝咖啡，或者早点离开，不被交通堵塞。
退一步想办法解决问题通常是好的。
还有一个办法！
找一只你喜欢的袜子。考虑所有相关特征：不同照明条件下的颜色、整体质量和耐久性、不同气候条件下的舒适性以及气味吸收。同样重要的是，它们在储存过程中不应失去弹性，所以天然织物是好的，它们应该可以用塑料包装。
如果左脚和右脚的袜子没有区别，那就更好了，但这并不重要。如果袜子是左右对称的，找到一双袜子是O（1）运算，而对袜子进行排序是近似的O（M）运算，其中M是你家里扔袜子的地方的数量，理想情况下是一个小常数。
如果你选择了一双左右袜子不同的奇装异服，对左脚和右脚的桶进行全桶排序，取O（N+M），其中N是袜子的数量，M与上述相同。其他人可以给出找到第一双袜子的平均迭代次数的公式，但通过盲搜索找到一双袜子的最坏情况是N/2+1，对于合理的N来说，这在天文学上是不太可能的。当用Mk1 Eyeball扫描一堆未分类的袜子时，使用先进的图像识别算法和启发式方法可以加快速度。
因此，实现O（1）袜子配对效率的算法（假设对称袜子）为：
你需要估计你的余生需要多少双袜子，或者直到你退休并搬到更温暖的气候，不再需要穿袜子。如果你还年轻，你还可以估计我们需要多长时间才能在家里拥有袜子分拣机器人，而整个问题变得无关紧要。您需要了解如何批量订购您选择的袜子，以及它的价格，以及它们的送货方式。订购袜子！扔掉你的旧袜子。
另一个步骤3将包括比较几年来一次购买几双同样数量的可能更便宜的袜子的成本，并加上整理袜子的成本。但我要保证：批量购买更便宜！此外，库存袜子的价值会随着股价的上涨而增加，这比你在很多投资中得到的要多。此外，还有存储成本，但袜子确实不会占用壁橱顶部货架上的空间。
问题已解决。所以，只要买一双新袜子，扔掉/捐赠你的旧袜子，在知道你的余生每天都在节省金钱和时间之后，就可以幸福地生活下去。
