昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
每当你拿起袜子时，把它放在一个地方。然后你拿起的下一只袜子，如果它与第一只袜子不匹配，就把它放在第一只袜子旁边。如果是，那就有一对。这样，有多少种组合其实并不重要，而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配，要么它没有匹配，这意味着你将它添加到数组中的一个位置。
这也意味着你几乎肯定不会把所有袜子都放在阵列中，因为袜子会在搭配时被取下。
其他回答
List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();
foreach (Sock newSock in UnsearchedSocks)
{
Sock MatchedSock = null;
foreach(Sock UnmatchedSock in UnmatchedSocks)
{
if (UnmatchedSock.isPairOf(newSock))
{
MatchedSock = UnmatchedSock;
break;
}
}
if (MatchedSock != null)
{
UnmatchedSocks.remove(MatchedSock);
PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
}
else
{
UnmatchedSocks.Add(NewSock);
}
}
我已经采取了简单的步骤，将我的努力减少到一个需要O（1）时间的过程中。
通过将我的输入减少到两种袜子中的一种（休闲用的白色袜子，工作用的黑色袜子），我只需要确定手中有哪种袜子。（从技术上讲，由于它们从未一起清洗过，我已将过程缩短到O（0）时间。）
为了找到合适的袜子，需要提前付出一些努力，并购买足够数量的袜子，以消除对现有袜子的需求。因为我在需要黑色袜子之前就已经做了这件事，所以我的努力很小，但里程可能会有所不同。
这种前期工作在非常流行和有效的代码中已经多次出现。示例包括#DEFINE'将圆周率定义为几个小数（其他示例也存在，但这是我现在想到的）。
这是基于比较的模型中的Omega（n log n）下限。（唯一有效的操作是比较两只袜子。）
假设你知道你的2n只袜子是这样排列的：
p1 p2 p3。。。pn pf（1）pf（2）。。。功率因数（n）
其中f是集合{1,2，…，n}的未知排列。知道这一点不会使问题变得更难。有n个！可能的输出（上半部分和下半部分之间的匹配），这意味着您需要log（n！）=Omega（n log n）比较。这可通过分类获得。
由于您对元素区别性问题的连接感兴趣：证明元素区别性的Omega（n log n）界限比较困难，因为输出是二进制的yes/no。这里，输出必须是匹配的，并且可能输出的数量足以获得一个合适的界限。然而，有一个变量与元素的区别有关。假设你有2n只袜子，想知道它们是否可以唯一配对。您可以通过将（a1，a2，…，an）发送到（a1，a1，a2、a2，…、an，an）来获得ED的缩减。（附带地，通过拓扑结构，ED的硬度证明非常有趣。）
我认为，如果只允许等式测试，那么原始问题应该有一个Omega（n2）边界。我的直觉是：考虑一个测试后添加边的图形，并认为如果图形不密集，则输出不是唯一确定的。
做一些预处理怎么样？我会在每只袜子上缝上一个标记或身份证号码，这样每双袜子都有相同的标记/身份证号码。这个过程可能在你每次买一双新袜子时都会完成。然后，您可以进行基数排序以获得O（n）总成本。为每个标记/身份证号码找一个位置，只需逐一挑选所有袜子并将它们放在正确的位置。
当我对袜子进行排序时，我会进行近似基数排序，将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近，我能看到一对完全匹配的袜子，否则我会在那一刻取出这双袜子。
几乎所有其他算法（包括usr评分最高的答案）排序，然后删除配对。我发现，作为一个人，一次考虑的袜子数量最好尽量减少。
我通过以下方式做到这一点：
挑选一只与众不同的袜子（在袜子堆里最先映入我眼帘的东西）。从概念位置开始基数排序，根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近，距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面，因为它是相同的，请在那里形成一对，然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。
这利用了人类在O（1）时间内进行模糊匹配的能力，这在某种程度上相当于在计算设备上建立哈希图。
通过先穿上与众不同的袜子，你可以留出空间来“放大”那些不那么与众不同的特征。
在去除了浅色、条纹袜子和三双长袜之后，你可能最终会得到大致按磨损程度分类的白色袜子。
在某种程度上，袜子之间的差异很小，以至于其他人不会注意到差异，因此不需要进一步的匹配。
