昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
袜子，无论是真的还是类似的数据结构，都将成对提供。
最简单的答案是，在允许袜子对分开之前，应该初始化袜子对的单个数据结构，该结构包含指向左右袜子的指针，从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。
这通过使用抽象层来消除任何计算配对问题。
将同样的想法应用于袜子配对的实际问题，显而易见的答案是：不要让你的袜子不配对。袜子是一双提供的，一双放在抽屉里（也许是把它们捆在一起），一双穿。但可能脱漆的地方是在洗衣机里，所以所需要的只是一个物理机制，让袜子保持在一起并有效地清洗。
有两种物理可能性：
对于一个“pair”对象，它保持指向每只袜子的指针，我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。
但是，为了让每一只袜子都能互相参照，有一个很好的解决方案：一个popper（如果你是美国人，可以使用“按扣”），比如：
http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html
然后，你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起，再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。
其他回答
考虑大小为“N”的哈希表。
如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）
我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章
让“N”对应于袜子独特颜色/图案数量的近似上限。
一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）
为了说明从一堆袜子中配对有多有效，我们必须首先定义机器，因为配对不是通过图灵或随机存取机器完成的，而随机存取机器通常用作算法分析的基础。
机器
机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的（希望是；-）。
我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制，由手臂或眼睛执行的操作具有非恒定的时间复杂性。这是因为我们不能用手臂移动一大堆无穷无尽的袜子，也不能用眼睛看到一大堆袜子上的袜子。
然而，机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。
因此，根据之前的分析，应按降序使用以下操作：
逻辑和算术运算环境读数环境改造
我们还可以利用这样一个事实，即人们只有非常有限的袜子。因此，环境改造可能涉及到所有袜子。
算法
我的建议是：
把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从2开始重复，直到无法配对。从1开始重复，直到地板上没有袜子。
操作4是必要的，因为当将袜子铺在地板上时，一些袜子可能会隐藏其他袜子。算法分析如下：
分析
该算法以高概率终止。这是由于在第二步中找不到袜子。
对于以下对n双袜子配对的运行时分析，我们假设在步骤1之后，至少有一半的2n双袜子没有隐藏。所以在平均情况下，我们可以找到n/2对。这意味着步骤4的循环执行了O（logn）次。步骤2执行O（n^2）次。因此，我们可以得出结论：
该算法涉及O（lnn+n）环境修改（步骤1 O（lnn）加上从地板上挑选每双袜子）该算法涉及步骤2中的O（n^2）个环境读数该算法包括O（n^2）个逻辑和算术运算，用于在步骤2中比较袜子和另一袜子
因此，我们的总运行时复杂度为O（r*n^2+w*（lnn+n）），其中r和w分别是合理数量袜子的环境读取和环境写入操作的因素。省略了逻辑运算和算术运算的成本，因为我们假设需要恒定数量的逻辑运算和算数运算来决定2只袜子是否属于同一对。这可能在每种情况下都不可行。
我希望我能为这个问题贡献一些新的东西。我注意到，所有的答案都忽略了这样一个事实，即在不降低整体洗衣性能的情况下，有两点可以执行预处理。
此外，即使是大家庭，我们也不需要假设有大量袜子。袜子从抽屉中取出并穿上，然后在洗衣服之前，将它们扔到一个地方（可能是一个垃圾箱）。虽然我不会将所说的垃圾箱称为后进先出堆栈，但我认为可以安全地假设
人们把两只袜子大致扔在箱子箱子在任何时候都不会随机化，因此从该容器顶部获取的任何子集通常都包含一双袜子。
由于我所知道的所有洗衣机的尺寸都是有限的（不管你要洗多少袜子），而且洗衣机中会发生实际的随机性，所以无论我们有多少袜子，我们总是有几乎不含单品的小子集。
我们的两个预处理阶段是“把袜子放在晾衣绳上”和“把袜子从晾衣绳里拿出来”，我们必须这样做，这样才能得到既干净又干燥的袜子。和洗衣机一样，晾衣绳是有限的，我假设我们可以看到袜子的整个部分。
以下是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堆栈的垃圾箱，一台有限的普通洗衣机，以及一条有限的普通晾衣绳——但这仍然适用于大量袜子。
关于并行性：只要你把两个袜子放在同一个箱子里，你就可以很容易地并行化所有这些步骤。
作为实际解决方案：
快速制作一堆易于区分的袜子。（用颜色表示）快速整理每一堆，并使用袜子的长度进行比较。作为一个人，你可以很快地决定用哪只袜子进行分区，以避免最坏的情况。（你可以看到多只袜子平行排列，这对你有利！）当垃圾堆达到一个阈值时，停止分类，在该阈值下，您可以立即找到不合适的袜子和短袜
如果你有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个以上的元素，且大小大致相等，那么与排序相比，排序的速度都会有所提高（前提是我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上快速进行。
整理n双袜子的问题是O（n）。在你把它们扔进洗衣篮之前，你先把左边的衣服穿到右边的衣服上。取出时，你剪下线，把每一对线放进抽屉里——对n对线进行2次操作，所以O（n）。
现在，下一个问题很简单，你是自己洗衣服，还是妻子洗衣服。这可能是一个完全不同领域的问题。：）
