成本：移动袜子->高，寻找/排队取袜子->小

我们要做的是减少移动次数，并通过增加搜索次数进行补偿。另外，我们可以利用智人的多线程环境来在决策缓存中保存更多的物品。

X = 你的，Y = 你配偶的

从一堆袜子A开始:

挑选两只袜子，将相应的X袜子放在X行，将Y袜子放在Y行的下一个可用位置。

重复以上操作直到A为空。

对于每行X和Y

1. 选择该行中的第一只袜子，沿着该行查找直到找到相应的袜子。

2. 将其放入相应的已完成袜子线路中。

3. 可选项 - 当你在查找该行时，如果当前袜子与上一个袜子相同，则对这些袜子执行步骤2。

作为步骤一的替代方案，您可以从该行中取出两个袜子而不是两个，由于缓存内存足够大，我们可以快速确定任何一个袜子是否与您正在观察的该行上的当前袜子匹配。如果你很幸运有三只手臂，那么在主体的记忆力足够大的情况下，你可能同时处理三只袜子。

直到X和Y都为空为止。

完成

然而，由于I/O（移动袜子）和搜索（在行中搜索袜子）的速度快，因此这个过程的复杂度与选择排序相似，但所花费的时间要少得多。

这是一个基于比较模型的Omega(n log n)下限。 (唯一有效的操作是比较两只袜子。)

假设你“知道”你的2n只袜子是这样排列的：

p₁ p₂ p₃ ... p_n p_f(1) p_f(2) ... p_f(n)

其中f是集合{1,2，…，n}的未知排列。知道这个对问题并没有更大的影响。有n!种可能的输出（第一半和第二半之间的匹配），这意味着您需要log(n!) = Omega(n log n)次比较。可以通过排序来实现。

由于您对元素唯一性问题的联系感兴趣：证明元素唯一性的Omega(n log n)下限更难，因为输出是二进制的是/否。在这里，输出必须是匹配，并且可能的输出数量足以得到合理的下限。但是，与元素唯一性相关的变体如下。假设您有2n只袜子，并想知道它们是否可以唯一配对。通过将(a₁, a₂, ..., a_n)发送到(a₁, a₁, a₂, a₂, ..., a_n, a_n)，可以从ED获得缩小。(顺便说一下，ED的难度证明非常有趣，通过拓扑学。)

如果只允许等式测试，则我认为原始问题应该有一个Omega(n²)下限。我的直觉是：考虑一个图，在测试后添加一条边，并论证如果该图不密集，则输出不能唯一确定。

现实世界的做法：

尽可能快地，一次从未分类的袜子堆中取出一只袜子，并将其放在你面前的堆中。这些堆应该相对紧凑地排列，所有袜子指向同一个方向；堆的数量受到您可以轻松触及的距离的限制。选择要放置袜子的堆应该是——尽可能快地——把一只袜子放在表面上与此类似的袜子堆上；偶尔会出现I型（将袜子放在不属于它的堆上）或II型（将袜子放在已有同类袜子的堆上）错误——最重要的考虑因素是速度。

一旦所有的袜子都在堆里，迅速检查多袜子堆，创建并移除成对的袜子（这些袜子将进入抽屉）。如果堆中有不匹配的袜子，则将它们重新放到最佳堆中（在尽可能快的约束条件下）。当所有多袜子堆被处理完毕后，匹配其余可成对的袜子，这些袜子由于II型错误而未能成对。嘘，你就完成了——我有很多袜子，直到其中的大部分变脏才洗它们。另一个实用的注意事项：我将一双袜子中的一只翻下来盖在另一只上面，利用它们的弹性特性，这样它们在被运送到抽屉和在抽屉中时就可以粘在一起。

• 从一堆袜子中随机抓取一只。
• 对于第一只袜子，或者如果之前选择的所有袜子都已经成对，只需将袜子放入你面前未成对袜子的“数组”中的第一个“插槽”中。
• 如果你有一只或多只已选择的未成对袜子，请将当前的袜子与数组中的所有未成对袜子进行比较。
  • 在构建数组时，可以将袜子分为一般类别或类型（白色/黑色，踝部/长筒，运动/正装），并且“逐层深入”，仅进行同类比较。
  • 如果找到可接受的匹配项，请将两只袜子放在一起并将它们从数组中删除。
  • 如果没有找到匹配项，请将当前袜子放入数组中的第一个空插槽中。
• 重复以上步骤，直到每只袜子都被配对。

这种方案的最坏情况是每一对袜子都足够不同，必须完全匹配，并且你选择的前n/2只袜子都不同。这是O（n²）情况，极其不太可能发生。如果袜子的唯一类型数t小于配对数p = n/2，并且每个类型的袜子足够相似（通常在磨损相关方面），那么如我上面所示，你需要比较的袜子数量最多为t，之后你拉出来的下一只袜子将与未成对的袜子之一匹配。这种情况在普通的袜子抽屉中更有可能发生，可以将最坏情况的复杂度降至O（n*t），通常t << n。

从您的问题中可以清楚地看出您在洗衣方面没有太多实际经验：）您需要一个适用于少量无法成对的袜子的算法。

到目前为止的答案没有充分利用我们人类的模式识别能力。 Set游戏提供了如何做到这一点的线索：将所有袜子放在二维空间中，以便您可以轻松地认识它们并用手轻松接近它们。 这将限制您的区域大约为120 * 80厘米左右。 然后选择您认可的双数并将其移除。 将额外的袜子放入空闲空间并重复此过程。 如果您为那些有易于识别的袜子（小孩子最容易想到）的人洗衣服，则可以通过首先选择这些袜子来进行基数排序。 当单只袜子数量较少时，此算法效果良好。

我已经采取了简单的步骤来将我的工作流程降低到只需要O(1)时间的过程。

通过将我的输入减少为两种袜子之一（白色袜子用于休闲，黑色袜子用于工作），我只需要确定手中有哪一双袜子即可。（从技术上讲，因为它们从未一起洗涤，我已将此过程降至O(0)时间。）

要找到理想的袜子并购买足够数量以消除您现有袜子的需求，需要一些前期的努力。由于在我需要黑色袜子之前就已经做过这件事情，所以我的努力很小，但是每个人的情况都不同。

这种前期的努力在非常受欢迎和有效的代码中已经出现了很多次。例如，#DEFINE将pi定义为几个小数位（还有其他例子，但这是我现在想到的一个）。

拿起第一只袜子，放在桌子上。现在再拿另一只袜子；如果它与第一只匹配，请将其放在第一只袜子的顶部。否则，请将其放在离第一只袜子有一小段距离的桌子上。接着拿第三只袜子；如果它与前两只中的任何一只匹配，请将其放在它们的顶部，否则请将其放在距第三只袜子有一小段距离的地方。重复这个过程，直到你把所有的袜子都拿完。

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);
  }
}

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

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

结果将有一个或两个堆：1. "匹配"和2. "缺失"

启发式方法:

1. 找到最不同的袜子。
2. 找到它的匹配项。
3. 如果没有匹配项，将其放在“缺失”堆中。
4. 重复从1开始，直到没有最不同的袜子为止。
5. 如果袜子少于6只，则转到11.
6. 将所有袜子盲目配对到它们的邻居（不要打包）
7. 找到所有匹配的对，打包并将打包的对移动到“匹配”堆中； 如果没有新的匹配项-将“index”加1
8. 如果“index”大于2（这可能是根据袜子数量而定的值，因为随着袜子数量的增加，将它们盲目配对的机会变少），则转到11.
9. 洗剩余的袜子
10. 转到1
11. 忘记“index”
12. 拿出一只袜子
13. 找到它的配对项
14. 如果该袜子没有配对项，则将其移动到“缺失”堆中
15. 如果找到匹配项，请将其配对，打包并将其移动到“匹配”堆中
16. 如果仍然有超过一只袜子，请转到12.
17. 如果只剩下一只袜子，请转到14.
18. 微笑满意:)

此外，还可以添加损坏袜子的检查，以便将其移除。它可以插入在第2和第3之间，以及第13和第14之间。

我期待听到任何经验或修正意见。

为了说明从一堆袜子中配对的效率有多高，我们必须先定义机器，因为配对不是通过图灵机或随机访问机进行的，这些通常用作算法分析的基础。

机器

该机器是真实世界元素“人”的抽象。它能够通过一双眼睛从环境中读取信息。我们的机器模型可以使用两只手臂来操作环境。逻辑和算术操作使用我们的大脑计算（希望如此;-)）。

我们还必须考虑使用这些工具可以执行的原子操作的本质运行时间。由于物理限制，由手臂或眼睛执行的操作具有非常数时间复杂度。这是因为我们不能用手臂移动无尽大的一堆袜子，眼睛也看不到无尽大的一堆袜子的顶部袜子。

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

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

• 逻辑和算术操作
• 环境读取
• 环境修改

我们还可以利用人们只有非常有限的袜子这一事实。因此，环境修改可以涉及堆中所有袜子。

算法

所以这是我的建议：

1. 将所有袜子散落在地面上。
2. 通过查看地面上的袜子找到一双袜子。
3. 重复步骤2直到无法匹配为止。
4. 从1开始重复，直到地面上没有袜子为止。

操作4是必要的，因为在将袜子散落在地面时，某些袜子可能会隐藏其他袜子。以下是该算法的分析：

分析

该算法高概率终止。这是由于在第2步中无法找到袜子配对。

对于配对n双袜子的运行分析，我们假设至少有一半的2n只袜子在步骤1后没有隐藏。因此，在平均情况下，我们可以找到n/2对。这意味着循环的第4步执行O(log n)次。步骤2执行O(n^2)次。因此，我们可以得出以下结论：

• 算法涉及O(ln n + n)个环境修改（步骤1包括O(ln n)个加上从地板上选取每对袜子）
• 算法涉及O(n^2)个环境读取（步骤2）
• 算法涉及O(n^2)个逻辑和算术操作以比较步骤2中的袜子

因此，我们有总运行复杂度为O(r*n^2 + w*(ln n + n))，其中r和w是合理数量的袜子的环境读取和环境写入操作的因素。逻辑和算术操作的成本被省略，因为我们假设判断两只袜子是否属于同一对需要恒定数量的逻辑和算术操作。这在每种情况下可能不可行。