从你的问题来看，你显然没有太多洗衣方面的实际经验：）。你需要一种算法，能很好地处理少量不可配对的袜子。

到目前为止，答案还没有充分利用我们的人类模式识别能力。集合游戏提供了如何做好这一点的线索：将所有袜子放在一个二维空间中，这样你就可以很好地识别它们，并用手轻松地够到它们。这将您的面积限制在120*80厘米左右。从那里选择您识别的配对并将其删除。将多余的袜子放在空闲空间，然后重复。如果你为穿着容易辨认的袜子的人洗衣服（脑海中浮现的是小孩子），你可以先选择袜子来进行基数排序。该算法仅在单袜子数量较少时有效

作为实际解决方案：

快速制作一堆易于区分的袜子。（用颜色表示）快速整理每一堆，并使用袜子的长度进行比较。作为一个人，你可以很快地决定用哪只袜子进行分区，以避免最坏的情况。（你可以看到多只袜子平行排列，这对你有利！）当垃圾堆达到一个阈值时，停止分类，在该阈值下，您可以立即找到不合适的袜子和短袜

如果你有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个以上的元素，且大小大致相等，那么与排序相比，排序的速度都会有所提高（前提是我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上快速进行。

为了说明从一堆袜子中配对有多有效，我们必须首先定义机器，因为配对不是通过图灵或随机存取机器完成的，而随机存取机器通常用作算法分析的基础。

机器

机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的（希望是；-）。

我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制，由手臂或眼睛执行的操作具有非恒定的时间复杂性。这是因为我们不能用手臂移动一大堆无穷无尽的袜子，也不能用眼睛看到一大堆袜子上的袜子。

然而，机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。

因此，根据之前的分析，应按降序使用以下操作：

逻辑和算术运算环境读数环境改造

我们还可以利用这样一个事实，即人们只有非常有限的袜子。因此，环境改造可能涉及到所有袜子。

算法

我的建议是：

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从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只袜子是否属于同一对。这可能在每种情况下都不可行。

我提出了另一个解决方案，它不会承诺更少的操作，也不会减少时间消耗，但应该尝试看看它是否能成为一个足够好的启发式方法，在大量袜子配对中提供更少的时间消耗。

前提条件：不能保证有相同的袜子。如果它们的颜色相同，并不意味着它们的大小或图案相同。袜子随机洗牌。袜子的数量可能是奇数（有些不见了，我们不知道有多少）。准备记住一个变量“index”并将其设置为0。

结果将有一个或两个桩：1。“匹配”和2。“缺少”

启发式：

找到最与众不同的袜子。找到匹配项。如果没有匹配项，请将其放在“缺失”堆上。从1开始重复。直到没有最与众不同的袜子。如果袜子少于6只，请转到11只。盲目地将所有袜子与邻居配对（不要打包）找到所有匹配的对，将其打包并将打包的对移动到“匹配”的堆中；如果没有新的匹配项-将“索引”增加1如果“index”大于2（这可能取决于袜子的值因为袜子数量越多盲目配对）进入11打乱其余的转到1忘记“索引”挑选一只袜子查找其配对如果没有袜子，就把它移到“失踪”的那一堆如果找到匹配项，将其配对，将其打包并移动到“匹配”堆中如果还有不止一只袜子，那就去12只如果只剩下一个，请转到14满意的微笑：）

此外，还可以添加检查袜子是否损坏，就像移除袜子一样。它可以插入2到3之间，13到14之间。

我期待听到任何经验或更正。

案例1：所有袜子都是一样的（顺便说一句，这是我在现实生活中所做的）。

选择其中的任意两个组成一对。恒定时间。

案例2：有固定数量的组合（所有权、颜色、大小、纹理等）。

使用基数排序。这只是线性时间，因为不需要比较。

情况3：组合的数量事先未知（一般情况）。

我们必须进行比较，以检查两只袜子是否成对。选择基于O（n log n）比较的排序算法之一。

然而，在现实生活中，当袜子的数量相对较少（恒定）时，这些理论上的优化算法将无法很好地工作。这可能比顺序搜索花费更多的时间，理论上需要二次时间。

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

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

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

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

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

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

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