如何有效地从一堆袜子中配对？

排序解决方案已经提出，但是排序有点过分：我们不需要顺序；我们只需要平等团体。

所以散列就足够了（而且更快）。

对于每种颜色的袜子，形成一堆。遍历输入篮中的所有袜子并将它们分配到颜色堆上。遍历每一堆并通过其他度量（例如图案）将其分配到第二组堆中递归地应用此方案，直到您将所有袜子分配到非常小的堆上，您可以立即进行可视化处理

这种递归哈希分区实际上是由 SQL Server 在需要对庞大的数据集进行哈希连接或哈希聚合时完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个 CPU。

如果您可以找到提供足够存储桶的分布键（散列键），并且每个存储桶足够小，可以非常快速地处理，则您不需要递归分区。不幸的是，我不认为袜子有这样的属性。

如果每只袜子都有一个名为“PairID”的整数，则可以根据PairID % 10（最后一位）轻松地将它们分配到 10 个桶中。

我能想到的最好的现实世界分区是创建一个一堆堆的矩形：一个维度是颜色，另一个是图案。为什么是长方形？因为我们需要 O(1) 随机访问堆。 （3D cuboid 也可以，但这不是很实用。）

更新：

并行性呢？多个人可以更快地匹配袜子吗？

最简单的并行化策略是让多个工作人员从输入篮中取出袜子并将袜子放在一堆堆上。这只扩大了这么多 - 想象一下 100 个人打了 10 堆。同步成本（表现为手部碰撞和人类交流）破坏了效率和加速（参见通用可扩展性法则！）。这容易出现死锁吗？不，因为每个工人一次只需要访问一堆。只有一个“锁”就不会出现死锁。取决于人类如何协调对桩的访问，活锁可能是可能的。他们可能只是使用随机退避，就像网卡在物理级别上做的那样，以确定哪些卡可以独占访问网络线。如果它适用于 NIC，那么它也应该适用于人类。如果每个工人都有自己的一堆堆，它几乎可以无限扩展。然后工作人员可以从输入篮中取出大块袜子（很少有争用，因为他们很少这样做）并且他们在分发袜子时根本不需要同步（因为他们有线程局部堆）。最后，所有工人都需要联合他们的桩组。如果工人形成聚合树，我相信可以在 O(log (工人计数 * 每个工人的堆数)) 中完成。

element distinctness problem 呢？正如文章所述，元素区别问题可以在 O(N) 中解决。袜子问题也是如此（还有 O(N)，如果你只需要一个分布步骤（我提出多个步骤只是因为人类不擅长计算 - 如果你在 md5(color, length, pattern, ...) 上分布，一个步骤就足够了，即 所有属性的完美哈希））。

显然，不能比 O(N) 更快，因此我们已经达到了最佳下限。

尽管输出不完全相同（在一种情况下，只是一个布尔值。在另一种情况下，袜子对），渐近复杂度是相同的。

---

由于人脑的结构与现代 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);
}

至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但它通常很丰富。

---

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

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

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

使用 radix sort。这只是线性时间，因为不需要比较。

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

我们必须进行比较以检查两只袜子是否成对出现。选择一种O(n log n)基于比较的排序算法。

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

---

非算法答案，但当我这样做时“高效”：

第 1 步）丢弃所有现有的袜子

第 2 步）去沃尔玛买 10-n 包白色和 m 包黑色。日常生活中不需要其他颜色。

然而有时，我不得不再次这样做（丢失的袜子，损坏的袜子等），而且我讨厌经常丢弃非常好的袜子（我希望他们继续销售相同的袜子参考！），所以我最近采取了一种不同的方法。

算法答案：

考虑一下，如果你只为第二叠袜子画一只袜子，就像你正在做的那样，在天真的搜索中找到匹配袜子的几率非常低。

所以随机挑选其中的五个，并记住它们的形状或长度。

为什么是五个？通常人类会记住工作记忆中五到七个不同的元素 - 有点像人类相当于 RPN 堆栈 - 五个是安全的默认值。

从 2n-5 的堆栈中取出一个。

现在在你画的五个里面寻找一个匹配（视觉模式匹配——人类擅长用小筹码），如果你没有找到一个，那么把它添加到你的五个中。

继续从堆叠中随机挑选袜子，并与您的 5+1 袜子进行比较。随着筹码量的增长，它会降低你的表现，但会提高你的胜算。快多了。

随意写下公式来计算您必须抽取多少个样本才能获得 50% 的匹配几率。 IIRC 这是一个超几何定律。

我每天早上都这样做，很少需要超过 3 次抽奖 - 但我有 n 对相似的（大约 10 对，给予或接受丢失的）m 形状的白色袜子。现在你可以估计我的股票的大小了:-)

顺便说一句，我发现每次需要一双袜子时，整理所有袜子的交易成本总和远低于一次绑定袜子的交易成本。准时制效果更好，因为这样您就不必绑定袜子，而且边际回报也会递减（也就是说，您一直在寻找那两三只袜子，当您在洗衣店的某个地方并且您需要完成匹配你的袜子，你会浪费时间）。

---

我所做的是拿起第一只袜子并放下（比如，放在洗衣盆的边缘）。然后我拿起另一只袜子，看看它是否和第一只袜子一样。如果是，我将它们都删除。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子并将其与前两只进行比较（如果它们还在那里）。等等。

假设“移除”袜子是一种选择，这种方法可以很容易地在数组中实现。实际上，您甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序（见下文），那么您可以移动它们并最终得到一个数组，其中所有袜子成对排列在数组中。

假设袜子的唯一操作是比较相等，这个算法基本上仍然是一个 n2 算法，虽然我不知道平均情况（从没学过计算）。

排序当然可以提高效率，尤其是在现实生活中，您可以轻松地将一只袜子“插入”到另外两只袜子之间。在计算中，同样可以通过一棵树来实现，但这是额外的空间。当然，我们又回到了 NlogN（或者更多，如果有几只袜子按照排序标准是相同的，但不是来自同一对）。

除此之外，我想不出任何东西，但这种方法在现实生活中似乎确实非常有效。 :)

---

这是在问错误的问题。正确的问题是，我为什么要花时间整理袜子？当您重视您选择的 X 个货币单位的空闲时间时，每年的费用是多少？

通常，这不仅仅是任何空闲时间，而是早上的空闲时间，您可以在床上度过，或者喝咖啡，或者早点离开而不被交通堵塞。

退后一步，想办法解决问题通常是件好事。

而且有办法！

找到你喜欢的袜子。考虑所有相关特征：不同照明条件下的颜色、整体质量和耐用性、不同气候条件下的舒适度以及异味吸收。同样重要的是，它们在储存时不应该失去弹性，所以天然织物是好的，它们应该用塑料包装。

如果左右脚袜没有区别就更好了，但这并不重要。如果袜子是左右对称的，找到一对是O(1)操作，排序袜子是近似O(M)操作，其中M是你房子里乱扔袜子的地方的数量，理想情况下是一些小的常数。

如果你选择了一双左右袜子不同的花哨，对左右脚桶进行全桶排序需要 O(N+M)，其中 N 是袜子的数量，M 同上。其他人可以给出找到第一对的平均迭代的公式，但是通过盲搜索找到一对的最坏情况是 N/2+1，对于合理的 N，这在天文上不太可能发生。这可以通过使用高级图像来加速当使用 Mk1 Eyeball 扫描一堆未分类的袜子时，识别算法和启发式算法。

因此，实现 O(1) 袜子配对效率（假设对称袜子）的算法是：

你需要估计你的余生需要多少双袜子，或者直到你退休并搬到气候温暖的地方，不再需要穿袜子。如果您还年轻，您还可以估计需要多长时间才能在我们家中拥有袜子分拣机器人，整个问题变得无关紧要。您需要了解如何批量订购您选择的袜子，成本是多少，以及它们是否送货。订购袜子！摆脱你的旧袜子。

另一个步骤 3 将涉及比较多年来一次购买几双相同数量的可能更便宜的袜子的成本，并增加分类袜子的成本，但相信我的话：批量购买更便宜！此外，存储中的袜子以股票价格上涨的速度增加价值，这比你在许多投资中得到的要多。再说一次，还有存储成本，但袜子在壁橱的顶部架子上确实不会占用太多空间。

问题解决了。所以，只要买新袜子，扔掉/捐出旧袜子，在知道你每天都在为你的余生节省金钱和时间之后，过上幸福的生活吧。

---

理论上的限制是 O(n)，因为您需要触摸每只袜子（除非有些已经以某种方式配对）。

您可以使用 radix sort 实现 O(n)。您只需要为存储桶选择一些属性。

首先，您可以选择（她的，我的） - 将它们分成 2 堆，然后使用颜色（可以有任何颜色顺序，例如按颜色名称的字母顺序） - 按颜色将它们分成堆（请记住保留步骤中的初始顺序1 代表同一堆中的所有袜子），然后是袜子的长度，然后是质地，......

如果您可以选择有限数量的属性，但有足够多的属性可以唯一地识别每一对，那么您应该在 O(k * n) 中完成，如果我们认为 k 是有限的，则为 O(n)。

---

作为一个实用的解决方案：

快速制作成堆易于区分的袜子。 （按颜色表示）对每一堆进行快速排序，并使用袜子的长度进行比较。作为人类，您可以相当快速地决定使用哪种袜子进行分区，以避免最坏的情况。 （你可以同时看到多只袜子，利用它来发挥你的优势！）当它们达到阈值时停止排序

如果你有 1000 只袜子，有 8 种颜色，平均分布，你可以在 c*n 时间内制作 4 堆每 125 只袜子。使用 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 是把袜子扔到一堆上的时间。

与大致只要 log(k) < x - 1 的任何 c*x*n + O(1) 方法相比，这种方法将是有利的。

在计算机科学中，这可能会有所帮助：我们有 n 个事物的集合，它们的顺序（长度）以及等价关系（额外信息，例如袜子的颜色）。等价关系允许我们对原始集合进行分区，并且在每个等价类中我们的顺序仍然保持不变。一个事物到它的等价类的映射可以在 O(1) 中完成，因此只需 O(n) 就可以将每个项目分配给一个类。现在我们已经使用了我们的额外信息，并且可以以任何方式对每个类进行排序。优点是数据集已经明显更小了。

该方法也可以嵌套，如果我们有多个等价关系 -> 制作颜色堆，而不是在纹理上的每个堆分区内，而不是按长度排序。任何创建具有超过 2 个大小相等的元素的分区的等价关系都将比排序带来速度提升（假设我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上非常快速地发生。

---

您正在尝试解决错误的问题。

解决方案1：每次将脏袜子放入洗衣篮时，将它们打成一个小结。这样您就不必在洗涤后进行任何分类。把它想象成在 Mongo 数据库中注册一个索引。为将来节省一些 CPU 做一些工作。

解决方案2：如果是冬天，你不必穿配套的袜子。我们是程序员。没有人需要知道，只要它有效。

解决方案 3：传播工作。您希望异步执行如此复杂的 CPU 进程，而不阻塞 UI。拿起那堆袜子，把它们塞进袋子里。仅在需要时才寻找一对。这样，它所花费的工作量就不会那么明显了。

希望这可以帮助！

---

这个问题其实是很哲学的。从本质上讲，它是关于人们解决问题的能力（我们大脑的“湿件”）是否等同于算法可以完成的事情。

袜子排序的一个明显算法是：

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

现在这个问题的计算机科学就是关于步骤的

“如果 s 与 N 中的袜子 t 配对”。我们能以多快的速度“记住”我们迄今为止所看到的？ “从 N 中删除 t”和“将 s 添加到 N”。跟踪我们迄今为止所见的成本有多高？

人类将使用各种策略来实现这些。 Human memory is associative，类似于哈希表，其中存储值的特征集与相应的值本身配对。例如，“红色汽车”的概念映射到一个人能够记住的所有红色汽车。具有完美记忆的人具有完美的映射。大多数人在这方面（以及大多数其他人）都是不完美的。关联映射的容量有限。映射可能在各种情况下哔不存在（一瓶啤酒太多），被错误记录（“我虽然她的名字是 Betty，而不是 Nettie”），或者即使我们观察到，也永远不会被覆盖事实已经改变（“爸爸的车”唤起了“橙色火鸟”，当我们真正知道他已经用它来换取红色卡马罗时）。

在袜子的情况下，完美回忆意味着查看袜子 s 总是会产生其兄弟 t 的记忆，包括足够的信息（它在熨衣板上的位置）以在恒定时间内定位 t。一个有过目不忘的人在一定时间内完成 1 和 2 都不会失败。

记忆力不够完美的人可能会根据他能够跟踪的特征使用一些常识等价类：大小（爸爸、妈妈、婴儿）、颜色（绿色、红色等）、图案（菱形、纯色等） , 风格（footie、膝盖高等）。因此，熨衣板将被划分为类别的部分。这通常允许通过内存在恒定时间内定位类别，但随后需要通过类别“桶”进行线性搜索。

完全没有记忆或想象力的人（对不起）只会把袜子放在一堆，然后对整堆进行线性搜索。

正如有人建议的那样，一个整洁的怪胎可能会使用数字标签来配对。这为全排序打开了大门，它允许人类使用与 CPU 完全相同的算法：二分查找、树、散列等。

因此，“最佳”算法取决于运行它的湿件/硬件/软件的质量，以及我们通过对成对施加总顺序来“作弊”的意愿。当然，“最好的”元算法是聘请世界上最好的袜子分类器：一个人或机器可以获取并快速存储大量 N 套袜子属性集在一个 1-1 关联存储器中，具有恒定的时间查找、插入、并删除。像这样的人和机器都可以采购。如果你有一只，你可以在 O(N) 时间内将所有袜子配对 N 对，这是最优的。总订单标签允许您使用标准散列来获得与人类或硬件计算机相同的结果。

---

成本：移动袜子 -> 高，查找/搜索排队的袜子 -> 小

我们要做的是减少移动次数，并用搜索次数进行补偿。此外，我们可以利用智人的多线程环境在决策缓存中保存更多的东西。

X = 你的，Y = 你的配偶

从所有袜子的 A 堆开始：

选择两只袜子，将对应的 X 袜子放在 X 线，Y 袜子放在 Y 线的下一个可用位置。

做直到 A 为空。

对于每行 X 和 Y

选择第一个袜子，沿着线搜索，直到找到对应的袜子。放入对应的成品袜线。可选 当您搜索该系列并且您正在查看的当前袜子与上一个相同时，请对这些袜子执行第 2 步。

作为第一步，您可以选择从该行拿起两只袜子而不是两只，因为缓存足够大，我们可以快速识别其中一只袜子是否与您正在观察的线上的当前一只袜子匹配。如果你有幸拥有三只手臂，考虑到主题的内存足够大，你可能会同时解析三只袜子。

直到 X 和 Y 都为空。

完毕

但是，由于这与选择排序具有相似的复杂性，因此由于 I/O（移动袜子）和搜索（搜索线以寻找袜子）的速度，所花费的时间要少得多。

---

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

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

p1 p2 p3 ... pn pf(1) pf(2) ... pf(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,一个_n）。 （顺便说一句，ED 的硬度证明非常有趣，via topology。）

我认为，如果您只允许相等性测试，那么原始问题应该有一个 Omega(n2) 界限。我的直觉是：考虑一个在测试后添加边的图形，并认为如果图形不密集，则输出不是唯一确定的。

---

现实世界的方法：

尽可能快地从未分类的一堆袜子中取出一只，然后将它们堆放在您面前。堆垛的布置应节省空间，所有袜子都指向同一方向；桩的数量受到您可以轻松到达的距离的限制。选择放袜子的堆垛应该——尽可能快地——把袜子放在一堆看起来很像的袜子上；可以容忍偶尔出现的 I 型（将袜子放在不属于它的一堆）或 II 型（当有一堆类似的袜子时，将袜子放在自己的一堆）错误——最重要的考虑因素是速度.

一旦所有的袜子都成堆，快速穿过多袜子堆，形成一双并取出它们（这些袜子正走向抽屉）。如果堆中有不匹配的袜子，请将它们重新堆成最好的（在尽可能快的约束内）堆。处理完所有多袜子堆后，匹配由于 II 类错误而未配对的剩余可配对袜子。嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗬嗬另一个实用说明：我将一双袜子的顶部向下翻转到另一只袜子上，利用它们的弹性特性，因此它们在被运送到抽屉时和在抽屉中时保持在一起。

---

对于 p 对袜子（n = 2p 单只袜子），我实际上是这样做的：

从那堆袜子中随机取出一只袜子。

对于第一只袜子，或者如果所有先前选择的袜子都已配对，只需将袜子放入您面前的未配对袜子“阵列”的第一个“插槽”中。

如果您有一只或多只选定的未配对袜子，请检查您当前的袜子与阵列中所有未配对的袜子。在构建您的阵列时，可以将袜子分为一般类别或类型（白色/黑色、脚踝/船员、运动/连衣裙），并“向下钻取”以仅比较同类。如果您找到可接受的匹配项，请将两只袜子放在一起并将它们从阵列中取出。如果不这样做，请将当前袜子放入阵列中的第一个开放插槽中。

在构建您的阵列时，可以将袜子分为一般类别或类型（白色/黑色、脚踝/船员、运动/连衣裙），并“向下钻取”以仅比较同类。

如果您找到可接受的匹配项，请将两只袜子放在一起并将它们从阵列中取出。

如果不这样做，请将当前袜子放入阵列中的第一个开放插槽中。

对每只袜子重复一次。

该方案的最坏情况是，每双袜子都不同，必须完全匹配，而且你挑选的前 n/2 只袜子都是不同的。这是您的 O(n2) 场景，而且极不可能。如果袜子的唯一类型数量 t 小于配对数量 p = n/2，并且每种类型的袜子足够相似（通常在与磨损相关的术语中），那么该类型的任何袜子都可以与任何其他，然后正如我在上面推断的那样，您必须比较的最大袜子数量是 t，之后您拉的下一个将匹配其中一只未配对的袜子。这种情况在普通袜子抽屉中比最坏情况更有可能发生，并将最坏情况的复杂性降低到 O(n*t)，其中通常 t << n。

---

从您的问题来看，很明显您对洗衣没有太多实际经验:)。您需要一种算法，该算法适用于少量不可配对的袜子。

到目前为止的答案并没有很好地利用我们的人类模式识别能力。 Set 游戏提供了如何做好这一点的线索：将所有袜子放在一个二维空间中，这样您既可以很好地识别它们，又可以用手轻松地拿到它们。这将您限制在大约 120 * 80 厘米左右的区域内。从那里选择您认识的对并删除它们。将额外的袜子放在空闲空间并重复。如果您为穿着易于识别的袜子的人（想到小孩子）洗衣服，您可以先选择那些袜子来进行基数排序。该算法仅在单只袜子数量较少时有效

---

拿起第一只袜子，放在桌子上。现在选择另一只袜子；如果它与第一个选择的匹配，则将其放在第一个之上。如果没有，请将其放在距离第一个不远的桌子上。选择第三只袜子；如果它与前两个中的任何一个匹配，请将其放在它们的顶部，或者将其放置在距第三个一小段距离的地方。重复，直到你拿起所有的袜子。

---

为了说明从一堆中配对袜子的效率有多高，我们必须首先定义机器，因为无论是通过图灵机还是随机存取机都不会完成配对，这通常用作算法分析。

机器

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

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

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

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

逻辑和算术运算

环境读数

环境改造

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

算法

所以这是我的建议：

将堆中的所有袜子铺在地板上。通过查看地板上的袜子找到一双。从 2 开始重复，直到无法配对为止。从 1 开始重复，直到地板上没有袜子。

操作 4 是必要的，因为当将袜子铺在地板上时，一些袜子可能会隐藏其他袜子。下面是算法分析：

分析

该算法以高概率终止。这是因为在第 2 步中找不到一双袜子。

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

该算法涉及 O(ln n + n) 环境修改（步骤 1 O(ln n) 加上从地板上挑选每双袜子）

该算法涉及来自步骤 2 的 O(n^2) 环境读取

该算法涉及 O(n^2) 逻辑和算术运算，用于在步骤 2 中将一只袜子与另一只袜子进行比较

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

---

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

---

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

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

结果会有一两堆：1.“匹配”和2.“缺失”

启发式：

寻找最有特色的袜子。找到它的匹配项。如果没有匹配，则将其放在“缺失”堆上。从 1. 重复，直到没有更多最有特色的袜子。如果袜子少于 6 只，则转到 11。将所有袜子盲目配对（不要打包） 找到所有配对的袜子，打包并将打包的配对移动到“匹配”堆；如果没有新匹配 - 将“index”增加 1 如果“index”大于 2（这可能是取决于袜子数量的值，因为袜子数量越多，盲目配对的机会就越小）转到 11 随机播放rest 转到 1 忘记“索引” 挑选一只袜子 找到它的一双 如果袜子没有一双，把它移到“丢失”堆 如果找到匹配，把它打包，打包并把它移到“匹配”堆 如果有还不止一只袜子去 12 如果只剩下一只去 14 微笑满意:)

此外，还可以检查损坏的袜子，就像将它们移除一样。它可以插入在 2 和 3 之间，以及 13 和 14 之间。

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

---

我已经采取了简单的步骤来减少我在花费 O(1) 时间的过程中的工作量。

通过将我的输入减少到两种袜子中的一种（休闲用白色袜子，工作用黑色袜子），我只需要确定我手头有两种袜子中的哪一种。 （从技术上讲，由于它们从不一起清洗，因此我将过程减少到 O(0) 时间。）

需要一些前期工作才能找到理想的袜子，并购买足够数量的袜子以消除对现有袜子的需求。正如我在需要黑色袜子之前所做的那样，我的努力很小，但里程可能会有所不同。

在非常流行和有效的代码中已经多次看到这种前期工作。示例包括#DEFINE'ing pi 到几位小数（存在其他示例，但这是现在想到的示例）。

---

当我对袜子进行分类时，我会做一个近似的radix sort，将袜子放在其他相同颜色/图案类型的袜子附近。除非我可以在我即将放下袜子的位置/附近看到完全匹配的情况，否则我会在该位置取出这对袜子。

几乎所有其他算法（包括 the top scoring answer by usr）排序，然后删除对。我发现，作为一个人，最好尽量减少一次考虑的袜子数量。

我这样做：

挑选一只与众不同的袜子（无论是什么东西首先引起我的注意）。通过基于与该袜子的相似性从堆中拉出袜子，从该概念位置开始基数排序。将新袜子放在当前桩附近，距离取决于它的不同程度。如果您发现自己将袜子放在另一个袜子上，因为它是相同的，请在那里形成一对，然后将它们取下。这意味着未来的比较将花费更少的精力来找到正确的位置。

这利用了人类在 O(1) 时间内进行模糊匹配的能力，这在某种程度上相当于在计算设备上建立哈希图。

通过首先拉出独特的袜子，您可以留出空间来“放大”不那么独特的特征。

在消除了荧光色、条纹袜和三双长袜之后，您最终可能会得到大部分是白色的袜子，大致按照它们的磨损程度来分类。

在某些时候，袜子之间的差异很小，以至于其他人不会注意到差异，并且不需要任何进一步的匹配工作。

---

每当你拿起一只袜子时，把它放在一个地方。然后你拿起下一只袜子，如果它与第一只袜子不匹配，把它放在第一只袜子旁边。如果是的话，有一对。这样一来，有多少组合并不重要，而且你拿起的每只袜子只有两种可能性——要么它有匹配的袜子已经在你的袜子阵列中，要么没有，这意味着你将其添加到数组中的某个位置。

这也意味着您几乎可以肯定永远不会将所有袜子放在阵列中，因为袜子会在匹配时被移除。

---

考虑一个大小为“N”的哈希表。

如果我们假设正态分布，那么将至少一个 sock 映射到一个存储桶的估计“插入”数为 NlogN（即，所有存储桶都已满）

我将其作为另一个谜题的一部分推导出来，但我很高兴被证明是错误的。 Here's my blog article on the same

让“N”对应于您拥有的袜子独特颜色/图案数量的近似上限。

一旦发生碰撞（又名：匹配），只需取下那双袜子。对下一批 NlogN 袜子重复相同的实验。它的美妙之处在于，由于人类思维的工作方式，您可以进行 NlogN 并行比较（冲突解决）。 :-)

---

袜子，无论是真实的还是一些类似的数据结构，都将成对提供。

最简单的答案是在允许分离对之前，应该已经初始化了该对的单个数据结构，其中包含指向左右袜子的指针，从而使袜子可以直接或通过它们的对被引用。袜子也可以扩展为包含指向其伙伴的指针。

这通过使用抽象层移除它来解决任何计算配对问题。

将相同的想法应用于配对袜子的实际问题，显而易见的答案是：永远不要让您的袜子不配对。袜子成对提供，成对放入抽屉（也许通过将它们捆绑在一起），成对穿着。但是，可以取消配对的地方是在洗衣机中，因此所需要的只是一种物理机制，可以让袜子保持在一起并有效地清洗。

有两种物理可能性：

对于保存指向每只袜子的指针的“pair”对象，我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。

但是对于每只袜子都保持对另一只袜子的引用，有一个巧妙的解决方案：popper（如果你是美国人，则为“按扣”），例如：

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

然后，您所做的就是在您脱下袜子并将它们放入洗衣篮后立即将它们合在一起，您再次消除了需要将袜子与“配对”概念的物理抽象配对的问题。

---

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

此外，我们不需要假设大量的袜子，即使对于大家庭也是如此。袜子从抽屉里拿出来穿上，然后扔到一个地方（可能是一个垃圾箱），然后再洗。虽然我不会将所说的 bin 称为 LIFO-Stack，但我会说可以安全地假设

人们将两只袜子大致扔在垃圾箱的同一区域，垃圾箱在任何时候都不是随机的，因此从这个垃圾箱顶部取出的任何子集通常都包含一对袜子。

由于我所知道的所有洗衣机的尺寸都是有限的（不管你要洗多少袜子），而实际的随机化发生在洗衣机中，无论我们有多少袜子，我们总是有小的子集，其中几乎没有单身人士。

我们的两个预处理阶段是“把袜子放在晾衣绳上”和“从晾衣绳上拿袜子”，为了得到不仅干净而且干燥的袜子，我们必须这样做。与洗衣机一样，晾衣绳是有限的，我假设我们将袜子放在视线范围内的整个部分。

这是 put_socks_on_line() 的算法：

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_remaining_clusters() 的算法：

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

在那之后，只剩下几只袜子了。这是我将之前未配对的袜子引入系统并在没有任何特殊算法的情况下处理剩余的袜子的地方 - 剩余的袜子非常少，并且可以非常快速地在视觉上处理。

对于所有剩余的袜子，我假设它们的对应物仍未洗涤并将它们放在下一次迭代中。如果您发现未配对的袜子随着时间的推移而增加（“袜子泄漏”），您应该检查您的垃圾箱 - 它可能会随机出现（您是否有猫在里面睡觉？）

我知道这些算法需要很多假设：一个充当某种 LIFO 堆栈的垃圾箱、一个有限的普通洗衣机和一个有限的普通晾衣绳——但这仍然适用于大量袜子。

关于并行性：只要你把两只袜子都扔进同一个箱子里，你就可以轻松地并行化所有这些步骤。

---

创建一个哈希表，用于不匹配的袜子，使用模式作为哈希。一件一件地遍历袜子。如果袜子在哈希表中有模式匹配，则将袜子从表中取出并配对。如果袜子没有火柴，就把它放到桌子上。

---

排序 n 对袜子的问题是 O(n)。在你把它们扔进洗衣篮之前，你把左边的一个穿到右边的一个。取出它们时，您剪断线并将每一对放入您的抽屉 - 对 n 对进行 2 次操作，所以 O(n)。

现在下一个问题只是你是否自己洗衣服而你的妻子洗她的衣服。这可能是一个完全不同的问题领域中的问题。 :)

---

如果“移动”操作相当昂贵，而“比较”操作很便宜，并且无论如何您都需要将整个集合移动到搜索比原始存储快得多的缓冲区中......只需将排序集成到强制性移动。

我发现将分类过程整合到悬挂晾干中变得轻而易举。无论如何，我都需要拿起每只袜子，然后把它挂起来（移动），把它挂在绳子上的特定位置几乎没有任何成本。现在只是不强制搜索整个缓冲区（字符串），我选择按颜色/阴影放置袜子。左边更黑，右边更亮，前面更彩色等等。现在，在我挂每只袜子之前，我会在它的“右侧附近”查看是否已经有匹配的袜子 - 这将“扫描”限制为 2-3 只其他袜子 - 如果是，我把另一个挂在它旁边。然后我把它们卷成对，同时从琴弦上取下，干燥时。

现在这似乎与最佳答案建议的“按颜色形成堆”并没有什么不同，但首先，通过不选择离散的堆而是范围，我可以毫无问题地将“紫色”归为“红色”或“蓝色”堆；它只是介于两者之间。然后通过集成两个操作（挂起干燥和排序），挂起时排序的开销大约是单独排序的 10%。

---

我刚刚完成了我的袜子配对，我发现最好的方法是：

选择其中一只袜子并将其收起来（为那双创建一个“桶”）

如果下一个是前一个的对，则将其放入现有存储桶中，否则创建一个新存储桶。

在最坏的情况下，这意味着您将有 n/2 个不同的桶，并且您将有 n-2 个关于哪个桶包含当前袜子的决定。显然，如果你只有几对，这个算法效果很好；我用 12 双做的。

它不是那么科学，但效果很好:)

---

我的解决方案并不完全符合您的要求，因为它正式需要 O(n)“额外”空间。但是，考虑到我的情况，它在我的实际应用中非常有效。因此，我认为这应该很有趣。

与其他任务结合

在我的情况下，特殊情况是我不使用烘干机，只是将我的衣服挂在普通的干衣机上。挂布需要 O(n) 操作（顺便说一下，我在这里总是考虑 bin packing 问题）并且问题本质上需要线性“额外”空间。当我从桶里拿出一只新袜子时，如果那双已经挂了，我会试着把它挂在它旁边。如果它是一双新袜子，我会在旁边留一些空间。

甲骨文机器更好;-)

它显然需要一些额外的工作来检查是否有匹配的袜子已经挂在某处，并且它将为计算机呈现系数约为 1/2 的解决方案 O(n^2)。但在这种情况下，“人为因素”实际上是一个优势——如果它已经挂起，我通常可以非常快速（几乎 O(1)）识别匹配的袜子（可能涉及一些难以察觉的脑内缓存）——考虑一下一种有限的“神谕”，如 Oracle Machine ;-) 在某些情况下，我们人类比数字机器具有这些优势 ;-)

几乎是 O(n)！

因此，将袜子配对问题与挂布问题联系起来，我免费获得 O(n)“额外空间”，并且有一个大约 O(n) 及时的解决方案，只需要比简单的挂布多一点工作，并且允许即使在一个非常糟糕的星期一早上，也能立即获得一双完整的袜子...... ;-)

---