我希望我能为这个问题贡献一些新的东西。我注意到，所有的答案都忽略了这样一个事实，即在不降低整体洗衣性能的情况下，有两点可以执行预处理。

此外，即使是大家庭，我们也不需要假设有大量袜子。袜子从抽屉中取出并穿上，然后在洗衣服之前，将它们扔到一个地方（可能是一个垃圾箱）。虽然我不会将所说的垃圾箱称为后进先出堆栈，但我认为可以安全地假设

人们把两只袜子大致扔在箱子箱子在任何时候都不会随机化，因此从该容器顶部获取的任何子集通常都包含一双袜子。

由于我所知道的所有洗衣机的尺寸都是有限的（不管你要洗多少袜子），而且洗衣机中会发生实际的随机性，所以无论我们有多少袜子，我们总是有几乎不含单品的小子集。

我们的两个预处理阶段是“把袜子放在晾衣绳上”和“把袜子从晾衣绳里拿出来”，我们必须这样做，这样才能得到既干净又干燥的袜子。和洗衣机一样，晾衣绳是有限的，我假设我们可以看到袜子的整个部分。

以下是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堆栈的垃圾箱，一台有限的普通洗衣机，以及一条有限的普通晾衣绳——但这仍然适用于大量袜子。

关于并行性：只要你把两个袜子放在同一个箱子里，你就可以很容易地并行化所有这些步骤。

由于人脑的结构与现代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”的哈希表。

如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为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只袜子是否属于同一对。这可能在每种情况下都不可行。

理论上的限制是O（n），因为你需要触摸每一只袜子（除非有些袜子已经配对）。

你可以用基数排序实现O（n）。你只需要为桶选择一些属性。

首先你可以选择（她的，我的）-把它们分成两堆，然后使用颜色（可以有任何颜色的顺序，例如按颜色名称的字母顺序）-按颜色将它们分成一堆（记住对同一堆中的所有袜子保持步骤1中的初始顺序），然后袜子的长度，然后是纹理，....

如果您可以选择有限数量的属性，但有足够多的属性可以唯一地标识每对属性，则应该使用O（k*n），如果我们可以考虑k是有限的，则使用O（n）。

正如许多作者所指出的，基数排序是一种有效的袜子排序方法。尚未提出的是一种完美的哈希方法。用每双袜子买来的时间来计算真是太麻烦了。在你购买袜子时，只需按顺序给袜子编号，就可以让你在整理袜子时把它们放在自己编号的抽屉里。

最多24双袜子的示例。请注意，较大的袜子隔层消除了将袜子卷在一起的需要，这就是所谓的速度/存储权衡。