昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
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
然后，你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起，再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。
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);
}
}
我希望我能为这个问题贡献一些新的东西。我注意到，所有的答案都忽略了这样一个事实，即在不降低整体洗衣性能的情况下，有两点可以执行预处理。
此外，即使是大家庭，我们也不需要假设有大量袜子。袜子从抽屉中取出并穿上，然后在洗衣服之前，将它们扔到一个地方（可能是一个垃圾箱）。虽然我不会将所说的垃圾箱称为后进先出堆栈，但我认为可以安全地假设
人们把两只袜子大致扔在箱子箱子在任何时候都不会随机化，因此从该容器顶部获取的任何子集通常都包含一双袜子。
由于我所知道的所有洗衣机的尺寸都是有限的（不管你要洗多少袜子），而且洗衣机中会发生实际的随机性，所以无论我们有多少袜子，我们总是有几乎不含单品的小子集。
我们的两个预处理阶段是“把袜子放在晾衣绳上”和“把袜子从晾衣绳里拿出来”，我们必须这样做，这样才能得到既干净又干燥的袜子。和洗衣机一样，晾衣绳是有限的，我假设我们可以看到袜子的整个部分。
以下是put_socks_on_ine（）的算法：
while (socks left in basket) {
take_sock();
if (cluster of similar socks is present) {
Add sock to cluster (if possible, next to the matching pair)
} else {
Hang it somewhere on the line, this is now a new cluster of similar-looking socks.
Leave enough space around this sock to add other socks later on
}
}
不要浪费时间四处移动袜子或寻找最佳搭配，这一切都应该在O（n）中完成，这也是我们将它们放在未分类的线上所需要的。袜子还没有配对，我们只有几个相似的簇。我们这里有一套有限的袜子是很有帮助的，因为这有助于我们创建“好”的簇（例如，如果这套袜子中只有黑色的袜子，那么按颜色簇就不是办法了）
下面是take_socks_from_line（）的算法：
while(socks left on line) {
take_next_sock();
if (matching pair visible on line or in basket) {
Take it as well, pair 'em and put 'em away
} else {
put the sock in the basket
}
我应该指出，为了提高其余步骤的速度，明智的做法是不要随机选择下一个袜子，而是从每个簇中依次选择一个又一个袜子。这两个预处理步骤只需要将袜子放在晾衣绳上或放在篮子里，这是我们无论做什么都必须做的，因此这将大大提高洗衣性能。
在此之后，很容易执行哈希分区算法。通常，大约75%的袜子已经配对，给我留下了非常小的袜子子集，并且这个子集已经（有点）聚类（在预处理步骤之后，我没有在我的篮子中引入太多熵）。另一件事是，剩余的集群往往足够小，可以一次处理，因此可以从篮子中取出整个集群。
下面是sort_maining_clusters（）的算法：
while(clusters present in basket) {
Take out the cluster and spread it
Process it immediately
Leave remaining socks where they are
}
之后，只剩下几只袜子了。在这里，我将之前未配对的袜子引入到系统中，并在不使用任何特殊算法的情况下处理剩余的袜子——剩余的袜子非常少，可以非常快速地进行视觉处理。
对于所有剩余的袜子，我假设它们的同伴仍然没有洗，并将它们放在一边，以备下次迭代。如果你记录了一段时间内未配对袜子的增长（“袜子泄漏”），你应该检查你的垃圾箱——它可能会随机出现（你有猫睡在里面吗？）
我知道这些算法需要很多假设：一个充当某种LIFO堆栈的垃圾箱，一台有限的普通洗衣机，以及一条有限的普通晾衣绳——但这仍然适用于大量袜子。
关于并行性：只要你把两个袜子放在同一个箱子里，你就可以很容易地并行化所有这些步骤。
我已经采取了简单的步骤，将我的努力减少到一个需要O（1）时间的过程中。
通过将我的输入减少到两种袜子中的一种（休闲用的白色袜子，工作用的黑色袜子），我只需要确定手中有哪种袜子。（从技术上讲，由于它们从未一起清洗过，我已将过程缩短到O（0）时间。）
为了找到合适的袜子，需要提前付出一些努力，并购买足够数量的袜子，以消除对现有袜子的需求。因为我在需要黑色袜子之前就已经做了这件事，所以我的努力很小，但里程可能会有所不同。
这种前期工作在非常流行和有效的代码中已经多次出现。示例包括#DEFINE'将圆周率定义为几个小数（其他示例也存在，但这是我现在想到的）。
从你的问题来看，你显然没有太多洗衣方面的实际经验：）。你需要一种算法，能很好地处理少量不可配对的袜子。
到目前为止，答案还没有充分利用我们的人类模式识别能力。集合游戏提供了如何做好这一点的线索：将所有袜子放在一个二维空间中，这样你就可以很好地识别它们，并用手轻松地够到它们。这将您的面积限制在120*80厘米左右。从那里选择您识别的配对并将其删除。将多余的袜子放在空闲空间，然后重复。如果你为穿着容易辨认的袜子的人洗衣服（脑海中浮现的是小孩子），你可以先选择袜子来进行基数排序。该算法仅在单袜子数量较少时有效
