昨天我从干净的洗衣店里把袜子配对，发现我这样做的方式不是很有效。我在做一个天真的搜索——挑选一只袜子并“迭代”这堆袜子以找到它的那双。这需要平均迭代 n/2 * n/4 = n 2 /8 个袜子。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/...）当然会想到实现 O(NlogN) 解决方案。
散列或其他非就地解决方案不是一种选择，因为我无法复制我的袜子（尽管如果可以的话可能会很好）。
所以，问题基本上是：
给定一堆n包含2n元素的袜子（假设每只袜子正好有一对匹配的对），用最多对数额外空间有效配对它们的最佳方法是什么？（如果需要，我相信我可以记住大量信息。）
我将感谢一个解决以下方面的答案：
排序解决方案已经提出，但是排序有点过分：我们不需要排序；我们只需要平等团体。
所以散列就足够了（而且更快）。
当 SQL Server 需要对庞大的数据集进行散列连接或散列聚合时，这种递归散列分区实际上是由SQL Server完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个 CPU。
如果您可以找到提供足够存储桶的分布键（散列键），并且每个存储桶足够小，可以非常快速地处理，则您不需要递归分区。不幸的是，我不认为袜子有这样的属性。
如果每只袜子都有一个名为“PairID”的整数，则可以根据PairID % 10（最后一位）轻松地将它们分配到 10 个桶中。
我能想到的最好的现实世界分区是创建一个矩形的桩：一个维度是颜色，另一个是图案。为什么是长方形？因为我们需要 O(1) 随机访问堆。（3D长方体也可以，但这不是很实用。）
更新：
并行性怎么样？多个人可以更快地匹配袜子吗？
元素区别问题呢？正如文章所述，元素区别问题可以在 中解决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：有恒定数量的组合（所有权、颜色、大小、纹理等）。
使用基数排序。这只是线性时间，因为不需要比较。
情况3：事先不知道组合的数量（一般情况）。
我们必须进行比较以检查两只袜子是否成对出现。选择一种O(n log n)基于比较的排序算法。
然而在现实生活中，当袜子的数量相对较少（恒定）时，这些理论上最优的算法就不能很好地工作。它可能需要比顺序搜索更多的时间，顺序搜索理论上需要二次时间。
非算法答案，但当我这样做时“高效”：
第 1 步）丢弃所有现有的袜子
第 2 步）去沃尔玛买 10-n 包白色和 m 包黑色。日常生活中不需要其他颜色。
然而有时，我不得不再次这样做（丢失的袜子，损坏的袜子等），而且我讨厌经常丢弃非常好的袜子（我希望他们继续销售相同的袜子参考！），所以我最近采取了一种不同的方法。
算法答案：
考虑一下，如果你只为第二叠袜子画一只袜子，就像你正在做的那样，在天真的搜索中找到匹配袜子的几率非常低。
为什么是五个？通常人类会记住工作记忆中五到七个不同的元素——有点像人类相当于RPN堆栈——五个是安全的默认值。
从 2n-5 的堆栈中取出一个。
现在在你画的五个里面寻找一个匹配（视觉模式匹配——人类擅长用小筹码），如果你没有找到一个，那么把它添加到你的五个中。
继续从堆叠中随机挑选袜子，并与您的 5+1 袜子进行比较。随着筹码量的增长，它会降低你的表现，但会提高你的胜算。快多了。
随意写下公式来计算您必须抽取多少个样本才能获得 50% 的匹配几率。IIRC 这是一个超几何定律。
我每天早上都这样做，而且很少需要超过 3 次抽奖 - 但我有n类似的（大约 10 对，给予或接受丢失的）m形状的白色袜子。现在你可以估计我的股票的大小了:-)
顺便说一句，我发现每次需要一双袜子时整理所有袜子的交易成本总和远低于一次绑定袜子的交易成本。准时制效果更好，因为这样您就不必绑定袜子，而且边际回报也在递减（也就是说，您一直在寻找在洗衣店某处时需要的两三只袜子完成匹配你的袜子，你会浪费时间）。
我所做的是拿起第一只袜子并放下（比如，放在洗衣盆的边缘）。然后我拿起另一只袜子，看看它是否和第一只袜子一样。如果是，我将它们都删除。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子并将其与前两只进行比较（如果它们还在那里）。等等。
假设“移除”袜子是一种选择，这种方法可以很容易地在数组中实现。实际上，您甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序（见下文），那么您可以移动它们并最终得到一个数组，其中所有袜子成对排列在数组中。
假设袜子的唯一操作是比较相等，这个算法基本上仍然是一个 n 2算法，虽然我不知道平均情况（从来没有学过计算）。
排序当然可以提高效率，尤其是在现实生活中，您可以轻松地将一只袜子“插入”到另外两只袜子之间。在计算中，同样可以通过一棵树来实现，但这是额外的空间。当然，我们又回到了 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) 。您只需要为存储桶选择一些属性。
如果您可以选择有限数量的属性，但有足够多的属性可以唯一地识别每一对，那么您应该在 O(k * n) 中完成，如果我们认为 k 是有限的，则为 O(n)。
作为一个实用的解决方案：
如果你有 1000 只袜子，有 8 种颜色，平均分布，你可以在 c*n 时间内制作 4 堆每 125 只袜子。使用 5 只袜子的阈值，您可以在 6 次运行中对每一堆进行分类。（数 2 秒，将袜子扔到正确的桩上，您将花费不到 4 小时。）
如果您只有 60 只袜子、3 种颜色和 2 种袜子（您的/您妻子的），您可以在 1 次运行中对每堆 10 只袜子进行分类（再次阈值 = 5）。（计数 2 秒将花费您 2 分钟）。
最初的桶排序将加快您的流程，因为它会及时将您的 n 个袜子分成 k 个桶，c*n因此您只需要做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 个大小相等的元素的分区的等价关系都将比排序带来速度提升（假设我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上非常快速地发生。
您正在尝试解决错误的问题。
解决方案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总是会产生对其兄弟姐妹的记忆t，包括足够的信息（它在熨衣板上的位置）以t在恒定时间内定位。一个有过目不忘的人在一定时间内完成 1 和 2 都不会失败。
记忆力不够完美的人可能会根据他能够跟踪的特征使用一些常识等价类：大小（爸爸、妈妈、婴儿）、颜色（绿色、红色等）、图案（菱形、纯色等） , 风格（footie、膝盖高等）。因此，熨衣板将被划分为类别的部分。这通常允许通过内存在恒定时间内定位类别，但随后需要通过类别“桶”进行线性搜索。
完全没有记忆或想象力的人（对不起）只会把袜子放在一堆，然后对整堆进行线性搜索。
正如有人建议的那样，一个整洁的怪胎可能会使用数字标签来配对。这为全排序打开了大门，它允许人类使用与 CPU 完全相同的算法：二分查找、树、散列等。
因此，“最佳”算法取决于运行它的湿件/硬件/软件的质量，以及我们通过对成对施加总顺序来“作弊”的意愿。当然，“最好的”元算法是聘请世界上最好的袜子分类器：一个人或机器可以获取并快速存储大量 N 套袜子属性集在一个 1-1 关联内存中，具有恒定的时间查找、插入、并删除。像这样的人和机器都可以采购。如果你有一只，你可以在 O(N) 时间内将所有袜子配对 N 对，这是最优的。总订单标签允许您使用标准散列来获得与人类或硬件计算机相同的结果。
这是基于比较的模型中的 Omega(n log n) 下限。（唯一有效的操作是比较两只袜子。）
假设你知道你的 2n 只袜子是这样排列的：
p 1 p 2 p 3 ... 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 1 , a 2 , ..., a n ) 发送到 (a 1 , a 1 , a 2 , a 2 , ..., a n , a n )从 ED 中获得减免。（顺便说一句，ED的硬度证明非常有趣，通过拓扑.)
我认为如果你只允许相等测试，应该有一个 Omega(n 2 ) 绑定到原始问题。我的直觉是：考虑一个在测试后添加边的图形，并认为如果图形不密集，则输出不是唯一确定的。
成本：移动袜子 -> 高，查找/搜索排队的袜子 -> 小
我们要做的是减少移动次数，并用搜索次数进行补偿。此外，我们可以利用智人的多线程环境在决策缓存中保存更多的东西。
X = 你的，Y = 你的配偶
从所有袜子的 A 堆开始：
选择两只袜子，将对应的 X 袜子放在 X 线，Y 袜子放在 Y 线的下一个可用位置。
做直到 A 为空。
对于每行 X 和 Y
选择第一个袜子，沿着线搜索，直到找到对应的袜子。
放入对应的成品袜线。
作为第一步，您可以选择从该行拿起两只袜子而不是两只，因为缓存足够大，我们可以快速识别其中一只袜子是否与您正在观察的线上的当前一只袜子匹配。如果你有幸拥有三只手臂，考虑到主题的内存足够大，你可能会同时解析三只袜子。
直到 X 和 Y 都为空。
完毕
但是，由于这与选择排序具有相似的复杂性，因此由于 I/O（移动袜子）和搜索（搜索线以寻找袜子）的速度，所花费的时间要少得多。
现实世界的方法：
尽可能快地从未分类的一堆袜子中取出一只，然后将它们堆放在您面前。堆垛的布置应节省空间，所有袜子都指向同一方向；桩的数量受到您可以轻松到达的距离的限制。选择放袜子的堆垛应该——尽可能快地——把袜子放在一堆看起来很像的袜子上；可以容忍偶尔出现的 I 型（将袜子放在不属于它的一堆）或 II 型（当有一堆类似的袜子时，将袜子放在自己的一堆）错误——最重要的考虑因素是速度.
一旦所有的袜子都成堆，快速穿过多袜子堆，形成一双并取出它们（这些袜子正走向抽屉）。如果堆中有不匹配的袜子，请将它们重新堆成最好的（在尽可能快的约束内）堆。处理完所有多袜子堆后，匹配由于 II 类错误而未配对的剩余可配对袜子。嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗖嗬嗬 另一个实用说明：我将一双袜子的顶部向下翻转到另一只袜子上，利用它们的弹性特性，因此它们在被运送到抽屉时和在抽屉中时保持在一起。
对于p对袜子（n = 2p个单独的袜子），我实际上是这样做的：
该方案的最坏情况是，每双袜子都不同，必须完全匹配，而且你挑选的前n/2只袜子都是不同的。这是您的O (n 2 ) 场景，而且极不可能。如果袜子t的唯一类型的数量小于配对的数量p = n/2，并且每种类型的袜子都足够相似（通常在与磨损相关的术语中），那么该类型的任何袜子都可以与任何其他，然后正如我在上面推断的那样，您必须比较的最大袜子数量是t，之后您拉下的袜子将匹配其中一只未配对的袜子。这种情况在普通袜子抽屉中比最坏情况更有可能发生，并将最坏情况的复杂性降低到O (n*t) ，其中通常t << n。
从您的问题来看，很明显您对洗衣没有太多实际经验:)。您需要一种算法，该算法适用于少量不可配对的袜子。
到目前为止的答案并没有很好地利用我们的人类模式识别能力。Set 游戏提供了如何做好这一点的线索：将所有袜子放在一个二维空间中，这样您既可以很好地识别它们，又可以用手轻松地拿到它们。这将您限制在大约 120 * 80 厘米左右的区域内。从那里选择您认识的对并删除它们。将额外的袜子放在空闲空间并重复。如果您为穿着易于识别的袜子的人（想到小孩子）洗衣服，您可以先选择那些袜子来进行基数排序。该算法仅在单只袜子数量较少时有效
拿起第一只袜子，放在桌子上。现在选择另一只袜子；如果它与第一个选择的匹配，则将其放在第一个之上。如果没有，请将其放在距离第一个不远的桌子上。选择第三只袜子；如果它与前两个中的任何一个匹配，请将其放在它们的顶部，或者将其放置在距第三个一小段距离的地方。重复，直到你拿起所有的袜子。
我提出了另一种解决方案，它不会承诺更少的操作，也不会减少时间消耗，但应该尝试看看它是否可以成为一个足够好的启发式方法，以在大量的袜子配对中提供更少的时间消耗。
前提条件： 不保证有相同的袜子。如果它们具有相同的颜色，并不意味着它们具有相同的尺寸或图案。袜子随机洗牌。袜子的数量可能是奇数（有些丢失，我们不知道有多少）。准备记住一个变量“索引”并将其设置为 0。
结果会有一两堆：1.“匹配”和2.“缺失”
启发式：
此外，还可以检查损坏的袜子，就像将它们移除一样。它可以插入在 2 和 3 之间，以及 13 和 14 之间。
我期待听到任何经验或更正。
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);
}
}
为了说明从一堆中配对袜子的效率有多高，我们必须首先定义机器，因为无论是通过图灵机还是随机存取机都不会完成配对，这通常用作算法分析。
机器是现实世界元素的抽象，称为人类。它能够通过一双眼睛从环境中读取信息。我们的机器模型能够通过使用 2 个手臂来操纵环境。逻辑和算术运算是使用我们的大脑计算的（希望 ;-)）。
我们还必须考虑可以使用这些工具执行的原子操作的内在运行时间。由于物理限制，由手臂或眼睛执行的操作具有非恒定的时间复杂度。这是因为我们不能用胳膊移动一大堆袜子，也不能用眼睛看到一大堆袜子上最上面的袜子。
然而，机械物理学也给了我们一些好处。我们不限于用一只手臂移动最多一只袜子。我们可以同时移动其中的两个。
因此，根据前面的分析，应按降序使用以下操作：
我们还可以利用人们只有非常有限数量的袜子这一事实。因此，环境改造可能涉及堆中的所有袜子。
所以这是我的建议：
操作 4 是必要的，因为当将袜子铺在地板上时，一些袜子可能会隐藏其他袜子。下面是算法分析：
该算法以高概率终止。这是因为在第 2 步中找不到一双袜子。
对于以下配对n袜子的运行时分析，我们假设2n在第 1 步之后至少有一半的袜子没有被隐藏。所以在平均情况下，我们可以找到n/2配对。这意味着循环是第 4 步执行的O(log n)次数。第 2 步是执行O(n^2)次数。所以我们可以得出结论：
O(ln n + n)环境修改（步骤 1O(ln n)加上从地板上挑选每双袜子）O(n^2)来自步骤 2 的环境读取O(n^2)逻辑和算术运算，用于在步骤 2 中将一只袜子与另一只袜子进行比较因此，对于合理数量的袜子，我们有一个总体运行时复杂性，O(r*n^2 + w*(ln n + n))分别是环境读取r和w环境写入操作的因素。省略了逻辑和算术运算的成本，因为我们假设需要恒定数量的逻辑和算术运算来确定 2 只袜子是否属于同一对。这可能并非在所有情况下都可行。
我已经采取了简单的步骤来减少我在花费 O(1) 时间的过程中的工作量。
通过将我的输入减少到两种袜子中的一种（休闲用白色袜子，工作用黑色袜子），我只需要确定我手头有两种袜子中的哪一种。（从技术上讲，由于它们从不一起清洗，因此我将过程减少到 O(0) 时间。）
需要一些前期工作才能找到理想的袜子，并购买足够数量的袜子以消除对现有袜子的需求。正如我在需要黑色袜子之前所做的那样，我的努力很小，但里程可能会有所不同。
在非常流行和有效的代码中已经多次看到这种前期工作。示例包括#DEFINE'ing pi 到几位小数（存在其他示例，但这是现在想到的示例）。
当我对袜子进行排序时，我会进行近似基数排序，将袜子放在相同颜色/图案类型的其他袜子附近。除非我可以在我即将放下袜子的位置/附近看到完全匹配的情况，否则我会在该位置取出这对袜子。
几乎所有其他算法（包括usr 得分最高的答案）排序，然后删除对。我发现，作为一个人，最好尽量减少一次考虑的袜子数量。
我这样做：
这利用了人类在 O(1) 时间内进行模糊匹配的能力，这在某种程度上相当于在计算设备上建立哈希图。
通过首先拉出独特的袜子，您可以留出空间来“放大”不那么独特的特征。
在去掉荧光色、条纹袜和三双长袜后，你可能会得到大部分是白色的袜子，大致按照它们的磨损程度来分类。
在某些时候，袜子之间的差异很小，以至于其他人不会注意到差异，并且不需要任何进一步的匹配工作。
考虑一个大小为“N”的哈希表。
如果我们假设正态分布，那么将至少一个 sock 映射到一个存储桶的估计“插入”数为 NlogN（即，所有存储桶都已满）
我将其作为另一个谜题的一部分推导出来，但我很高兴被证明是错误的。 这是我的博客文章
让“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)操作（顺便说一下，我在这里总是考虑装箱问题），问题本质上需要线性“额外”空间。当我从桶里拿出一只新袜子时，如果那双已经挂了，我会试着把它挂在它旁边。如果它是一双新袜子，我会在旁边留一些空间。
显然需要一些额外的工作来检查是否有匹配的袜子已经挂在某个地方，它会为计算机O(n^2)提供系数约为的解决方案。1/2但在这种情况下，“人为因素”实际上是一个优势——O(1)如果它已经挂起，我通常可以非常快速（几乎）识别匹配的袜子（可能涉及一些难以察觉的脑内缓存）——认为它是一种有限的“oracle”，如Oracle Machine ;-) 在某些情况下，我们人类比数字机器具有这些优势 ;-)
O(n)！因此，将袜子配对问题与挂布问题联系起来，我O(n)免费获得“额外空间”，并且有一个O(n)及时的解决方案，只需要比简单的挂布多一点工作，并允许立即访问整双即使在一个非常糟糕的星期一早上也穿袜子...... ;-)
做一些预处理怎么样？我会在每只袜子上缝上一个标记或 ID 号，使每对都具有相同的标记/ID 号。每次您购买新袜子时，都可能会执行此过程。然后，您可以进行基数排序以获得 O(n) 总成本。为每个标记/ID 编号找到一个位置，然后将所有袜子一件一件地挑选出来，然后将它们放入正确的位置。
在我攻读博士学位（计算机科学）期间，我经常想到这一点。我想出了多种解决方案，这取决于区分袜子的能力，从而尽快找到正确的袜子对。
假设查看袜子并记住其独特图案的成本可以忽略不计（ε）。那么最好的解决办法就是把所有袜子都扔在桌子上。这涉及以下步骤：
这确实是最快的可能性，并且以 n + 1 = O(n) 复杂度执行。但它假设你完全记得所有模式......实际上，情况并非如此，我个人的经验是，你有时在第一次尝试时找不到匹配的对：
这现在取决于我们找到匹配对的能力。如果您有通常具有非常相似图案的深色/灰色双或白色运动袜，则尤其如此！让我们承认你有 P 的概率找到相应的袜子。在找到相应的袜子以形成一双之前，您平均需要 1/P 尝试。总体复杂度为 1 + (n/2) * (1 + 1/P) = O(n)。
两者在袜子数量上都是线性的，并且是非常相似的解决方案。让我们稍微修改一下这个问题，承认你在套装中有多双相似的袜子，并且很容易一次存储多双袜子(1+ε)。对于 K 个不同的模式，您可以实现：
整体复杂度变为 n+K = O(n)。它仍然是线性的，但选择正确的算法现在可能很大程度上取决于 P 和 K 的值！但是有人可能会再次反对，您可能很难为每只袜子找到（或创建）集群。
此外，您还可以通过在网站上查看最佳算法并提出自己的解决方案来节省时间:)
前提条件
算法
尝试：
除了：
桌子不够大：
小心地将所有未配对的袜子混合在一起，然后恢复操作
//此操作将导致新堆和空桌子
桌子上没有袜子了：
扔（最后一只无法配对的袜子）
没有袜子留在堆里：
退出洗衣房
最后：
已知的问题
如果周围没有桌子或桌子上没有足够的空间容纳至少一只袜子，该算法将进入无限循环。
可能的改进
根据要分类的袜子数量，如果有足够的空间，可以通过对桌子上的袜子进行分类来增加吞吐量。
为了使它起作用，需要一个属性，该属性对每双袜子都有一个唯一的值。这样的属性可以很容易地从袜子的视觉属性中合成。
按所述属性对桌子上的袜子进行排序。我们称该属性为“颜色”。将袜子排成一排，将深色袜子放在右侧（即 .push_back()），将浅色袜子放在左侧（即 .push_front()）
对于大堆，尤其是以前看不见的袜子，属性合成可能需要大量时间，因此吞吐量会明显下降。但是，这些属性可以保存在内存中并重复使用。
需要进行一些研究来评估这种可能的改进的效率。出现以下问题：
PoC 符合MCVE指南：
#include <iostream>
#include <vector>
#include <string>
#include <time.h>
using namespace std;
struct pileOfsocks {
pileOfsocks(int pairCount = 42) :
elemCount(pairCount<<1) {
srand(time(NULL));
socks.resize(elemCount);
vector<int> used_colors;
vector<int> used_indices;
auto getOne = [](vector<int>& v, int c) {
int r;
do {
r = rand() % c;
} while (find(v.begin(), v.end(), r) != v.end());
v.push_back(r);
return r;
};
for (auto i = 0; i < pairCount; i++) {
auto sock_color = getOne(used_colors, INT_MAX);
socks[getOne(used_indices, elemCount)] = sock_color;
socks[getOne(used_indices, elemCount)] = sock_color;
}
}
void show(const string& prompt) {
cout << prompt << ":" << endl;
for (auto i = 0; i < socks.size(); i++){
cout << socks[i] << " ";
}
cout << endl;
}
void pair() {
for (auto i = 0; i < socks.size(); i++) {
std::vector<int>::iterator it = find(unpaired_socks.begin(), unpaired_socks.end(), socks[i]);
if (it != unpaired_socks.end()) {
unpaired_socks.erase(it);
paired_socks.push_back(socks[i]);
paired_socks.push_back(socks[i]);
}
else
unpaired_socks.push_back(socks[i]);
}
socks = paired_socks;
paired_socks.clear();
}
private:
int elemCount;
vector<int> socks;
vector<int> unpaired_socks;
vector<int> paired_socks;
};
int main() {
pileOfsocks socks;
socks.show("unpaired socks");
socks.pair();
socks.show("paired socks");
system("pause");
return 0;
}
正如许多作者所指出的，基数排序是一种对袜子进行排序的有效方法。尚未提出的是一种完美的散列方法。使用购买每双袜子的时间就是这样一个哈希值。只需在购买袜子时按顺序对袜子进行编号，您就可以将它们放在自己编号的抽屉中。
最多 24 双袜子的示例。请注意，较大的袜子隔间消除了将袜子卷在一起的需要，即所谓的速度/存储折衷。
我提出的解决方案假设所有袜子在细节上都是相同的，除了颜色。如果袜子之间有更多细节需要延迟，这些细节可用于定义不同类型的袜子，而不是我的示例中的颜色。
假设我们有一堆袜子，一只袜子可以有三种颜色：蓝色、红色或绿色。
然后我们可以为每种颜色创建一个并行工作者；它有自己的列表来填充相应的颜色。
At time i:
Blue read Pile[i] : If Blue then Blue.Count++ ; B=TRUE ; sync
Red read Pile[i+1] : If Red then Red.Count++ ; R=TRUE ; sync
Green read Pile [i+2] : If Green then Green.Count++ ; G=TRUE ; sync
带同步过程：
Sync i:
i++
If R is TRUE:
i++
If G is TRUE:
i++
这需要初始化：
Init:
If Pile[0] != Blue:
If Pile[0] = Red : Red.Count++
Else if Pile[0] = Green : Green.Count++
If Pile[1] != Red:
If Pile[0] = Green : Green.Count++
在哪里
Best Case: B, R, G, B, R, G, .., B, R, G
Worst Case: B, B, B, .., B
Time(Worst-Case) = C * n ~ O(n)
Time(Best-Case) = C * (n/k) ~ O(n/k)
n: number of sock pairs
k: number of colors
C: sync overhead
两条思路，查找任何匹配项所需的速度，与查找所有匹配项所需的速度与存储相比。
对于第二种情况，我想指出一个 GPU 并行版本，它会查询袜子的所有匹配项。
如果您有多个要匹配的属性，您可以使用分组元组和更高级的 zip 迭代器以及推力的变换函数，虽然这里是一个简单的基于 GPU 的查询：
//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>
// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator GpuListIterator;
template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
ColoredSockQuery( int colorToSearch )
{ SockColor = colorToSearch; }
int SockColor;
__host__ __device__
bool operator()(T x)
{
return x == SockColor;
}
};
struct GenerateRandomSockColor
{
float lowBounds, highBounds;
__host__ __device__
GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};
__host__ __device__
int operator()(const unsigned int n) const
{
thrust::default_random_engine rng;
thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
rng.discard(n);
return dist(rng);
}
};
template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
typedef typename std::iterator_traits<GpuListIterator>::value_type T;
std::cout << name << ": ";
thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
std::cout << "\n";
}
int main()
{
int numberOfSocks = 10000000;
GpuList socks(numberOfSocks);
thrust::transform(thrust::make_counting_iterator(0),
thrust::make_counting_iterator(numberOfSocks),
socks.begin(),
GenerateRandomSockColor(0, 200));
clock_t start = clock();
GpuList sortedSocks(socks.size());
GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
socks.end(),
sortedSocks.begin(),
ColoredSockQuery<int>(2));
clock_t stop = clock();
PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);
double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
std::cout << "Time elapsed in ms: " << elapsed << "\n";
return 0;
}
//nvcc -std=c++11 -o test test.cu
1000 万只袜子的运行时间：9 毫秒
如果您可以将一对袜子抽象为键本身并将另一对袜子抽象为值，我们就可以使用散列来发挥我们的杠杆作用。
在地板上画出你身后的两个假想部分，一个给你，另一个给你的配偶。
从一堆袜子中取出一只。
现在按照以下规则将袜子一只一只地放在地板上。
确定袜子是你的还是她的，然后查看地板上的相关部分。
如果你能在地板上看到这对，就把它捡起来打结或夹起来，或者在你找到一对后做任何你想做的事情，然后把它放在一个篮子里（把它从地板上取下来）。
将其放在相关部分。
重复 3 直到所有袜子都从堆中取出。
散列和抽象
抽象是一个非常强大的概念，已被用于改善用户体验 (UX)。在现实生活中与计算机交互的抽象示例包括：
散列或其他非就地解决方案不是一种选择，因为我无法复制我的袜子（尽管如果可以的话可能会很好）。
我相信提问者正在考虑应用散列，以便在放置它们之前应该知道任何一对袜子所在的插槽。
这就是为什么我建议将放在地板上的单个袜子抽象为哈希键本身（因此不需要复制袜子）。
如何定义我们的哈希键？
如果有不止一对类似的袜子，我们的密钥的以下定义也将起作用。也就是说，假设有两双黑人男袜 PairA 和 PairB，每双袜子分别命名为 PairA-L、PairA-R、PairB-L、PairB-R。所以PairA-L可以和PairB-R配对，但是PairA-L和PairB-L不能配对。
假设任何袜子都可以通过以下方式唯一识别，
Attribute[Gender] + Attribute[Colour] + Attribute[Material] + Attribute[Type1] + Attribute[Type2] + Attribute[Left_or_Right]
这是我们的第一个哈希函数。让我们为此使用一个简短的符号h1(G_C_M_T1_T2_LR)。h1(x)不是我们的位置键。
另一个消除 Left_or_Right 属性的散列函数是h2(G_C_M_T1_T2). 第二个函数h2(x)是我们的位置键！（对于您身后地板上的空间）。
注意：由于我们在找到一对时删除了一对，因此可以安全地假设最多只有一个具有唯一 h2(x) 或 h1(x) 值的插槽。
如果我们每只袜子都只有一对匹配，则使用 h2(x) 查找位置，如果没有配对，则需要检查，因为可以安全地假设它们是一对。
为什么把袜子放在地板上很重要
让我们考虑这样一种情况，即袜子彼此堆叠成一堆（最坏的情况）。这意味着我们别无选择，只能进行线性搜索以找到一对。
将它们散布在地板上可以提高可见度，从而提高发现匹配袜子的机会（匹配哈希键）。在第 3 步中，当一只袜子放在地板上时，我们的大脑已经下意识地记录了这个位置。- 所以如果这个位置在我们的记忆中可用，我们可以直接找到匹配的对。- 如果位置不记得了，别担心，我们可以随时恢复线性搜索。
为什么从地板上取下这对很重要？
分析
我说的是比较操作，从一堆中挑选袜子必然是 n 次操作。因此，实际的下限将是 n 次迭代和 n/2 次比较。
加快速度
为了获得一个完美的分数，以便 Derp 获得 O(n/2) 比较，我会推荐 Derpina，
这是否等同于元素区别问题？
我建议的方法是用于解决元素区别问题的方法之一，您将它们放在哈希表中并进行比较。
鉴于您只存在一对精确对的特殊情况，它已变得非常等同于元素不同问题。因为我们甚至可以对袜子进行分类并检查相邻的袜子是否成对（EDP 的另一种解决方案）。
但是，如果给定的袜子可能存在不止一对，则它会偏离 EDP。