昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
案例1：所有袜子都是一样的（顺便说一句，这是我在现实生活中所做的）。
选择其中的任意两个组成一对。恒定时间。
案例2：有固定数量的组合（所有权、颜色、大小、纹理等）。
使用基数排序。这只是线性时间，因为不需要比较。
情况3：组合的数量事先未知（一般情况）。
我们必须进行比较，以检查两只袜子是否成对。选择基于O（n log n）比较的排序算法之一。
然而，在现实生活中，当袜子的数量相对较少（恒定）时，这些理论上的优化算法将无法很好地工作。这可能比顺序搜索花费更多的时间，理论上需要二次时间。
其他回答
每当你拿起袜子时，把它放在一个地方。然后你拿起的下一只袜子，如果它与第一只袜子不匹配，就把它放在第一只袜子旁边。如果是，那就有一对。这样，有多少种组合其实并不重要，而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配，要么它没有匹配，这意味着你将它添加到数组中的一个位置。
这也意味着你几乎肯定不会把所有袜子都放在阵列中，因为袜子会在搭配时被取下。
由于人脑的结构与现代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);
}
至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但通常很丰富。
我刚刚完成袜子配对，我发现最好的方法是：
选择一只袜子并将其收起来（为这双袜子创建一个“水桶”）如果下一个是上一个的一对，则将其放到现有的存储桶中，否则创建一个新的存储桶。
在最坏的情况下，这意味着您将有n/2个不同的存储桶，并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然，如果你只有几对，这个算法会很好地工作；我用了12双鞋。
它不是那么科学，但它工作得很好：）
作为实际解决方案：
快速制作一堆易于区分的袜子。（用颜色表示）快速整理每一堆，并使用袜子的长度进行比较。作为一个人，你可以很快地决定用哪只袜子进行分区，以避免最坏的情况。（你可以看到多只袜子平行排列，这对你有利！）当垃圾堆达到一个阈值时，停止分类，在该阈值下，您可以立即找到不合适的袜子和短袜
如果你有1000只袜子，有8种颜色，平均分布，你可以在c*n时间内每125只袜子做4堆。以5只袜子为阈值，你可以在6次跑步中对每一堆袜子进行分类。（数2秒把袜子扔到正确的堆上，只需要不到4小时。）
如果你只有60只袜子、3种颜色和2种袜子（你/你妻子的），你可以在1次跑步中对每一堆10只袜子进行分类（同样阈值=5）。（数2秒，需要2分钟）。
最初的桶排序将加快您的进程，因为它在c*n时间内将n个袜子分成k个桶，因此您只需执行c*n*log（k）工作。（不考虑阈值）。所以，你所做的所有关于n*c*（1+log（k））的工作，其中c是把袜子扔在一堆上的时间。
与任何c*x*n+O（1）方法相比，只要log（k）<x-1，该方法将是有利的。
在计算机科学中，这可能很有用：我们有一个n个事物的集合，它们的顺序（长度）和等价关系（额外的信息，例如袜子的颜色）。等价关系允许我们对原始集合进行分区，并且在每个等价类中我们的顺序仍然保持不变。一个事物到它的等价类的映射可以在O（1）中完成，因此只需要O（n）就可以将每个项分配给一个类。现在我们已经使用了额外的信息，可以以任何方式对每个类进行排序。其优点是数据集已经明显更小。
该方法也可以嵌套，如果我们有多个等价关系->使颜色堆积，而不是在纹理上的每个堆积分区内，而不是按长度排序。任何等价关系如果创建一个分区，其中包含2个以上的元素，且大小大致相等，那么与排序相比，排序的速度都会有所提高（前提是我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上快速进行。
对于p双袜子（n=2p只袜子），我实际上是这样做的：
从袜子堆里随便拿一只袜子。对于第一只袜子，或者如果之前选择的所有袜子都已配对，只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子，请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时，可以将袜子分为普通类别或类型（白色/黑色、脚踝/圆领、运动型/连衣裙），并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配，把两只袜子放在一起，然后把它们从阵列中去掉。如果没有，请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。
这种方案的最坏情况是，每双袜子都不同，必须完全匹配，而且你挑选的第一双n/2袜子都不同。这是你的O（n2）场景，极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2，并且每种类型的袜子都足够相似（通常在穿着相关的术语中），使得该类型的任何袜子都可以与任何其他袜子配对，那么正如我上面所推断的，你必须与之进行比较的袜子的最大数量是t，之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生，并将最坏情况的复杂性降低到O（n*t），其中通常t<<n。
