昨天我把干净的洗衣店的袜子配对，弄清楚我做的方式效率不高。我正在做一个天真的搜索 - 挑选一个袜子并“迭代”堆，以找到它的对。这需要迭代n / 2 * n / 4 = n2/平均8个袜子。
作为一名计算机科学家，我在想我能做些什么？当然，为了实现O（NlogN）解决方案，我们会想到排序（根据大小/颜色/ ...）。
哈希或其他非就地解决方案不是一种选择，因为我无法复制我的袜子（尽管如果可能的话可能会很好）。
所以，问题基本上是：
给了一堆 n 一双袜子，含有 2n 元素（假设每个袜子只有一个匹配对），有效配对它们的最佳方法是什么？ （我相信如果需要，我会记住那些信息。）
我将感谢一个解决以下方面的答案：
已经提出了分类解决方案，但是 排序有点太多了：我们不需要订单; 我们只需要平等团体。
所以 散列 就足够了（而且速度更快）。
这种递归散列分区实际上是由 SQL Server 当它需要在大型数据集上散列连接或散列聚合时。它将构建输入流分配到许多独立的分区中。该方案可以线性扩展到任意数量的数据和多个CPU。
如果可以找到分发键（散列键），则不需要递归分区 提供足够的水桶 每个桶都很小，可以很快处理。不幸的是，我不认为袜子有这样的属性。
如果每个袜子都有一个名为“PairID”的整数，那么根据它可以很容易地将它们分配到10个桶中 PairID % 10 （最后一位数字）。
我能想到的最好的真实分区是创建一个 长方形的桩：一个是颜色，另一个是图案。为什么是矩形？因为我们需要O（1）随机访问桩。 （3D 长方体 也会有用，但那不太实用。）
更新：
关于什么 排比？多个人可以更快地匹配袜子吗？
关于 元素清晰度问题？正如文章所述，元素清晰度问题可以解决 O(N)。袜子问题也是如此（同样如此） O(N)，如果你只需要一个分配步骤（我提出了多个步骤只是因为人类计算不好 - 如果你分发的话，一步就够了 md5(color, length, pattern, ...)，即a 完美哈希 所有属性））。
显然，人们不能走得更快 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步）去 沃尔玛（Walmart） 并通过10-n包的数据包购买 白色和米包黑色。每天都不需要其他颜色 生活。
然而有时候，我必须再次这样做（丢失袜子，损坏的袜子等），我不喜欢经常丢弃完美的袜子（我希望他们继续销售相同的袜子参考！），所以我最近采取了一种不同的方法。
算法答案：
考虑一下，如果你只为第二叠袜子画一个袜子，就像你在做的那样，你在天真的搜索中找到匹配的袜子的几率非常低。
为什么五个？通常人类是好的，记住工作记忆中的五到七个不同的元素 - 有点像人类的等同于一个 RPN stack - five是一个安全的默认值。
从2n-5的筹码中挑选一个。
现在寻找一个匹配（视觉模式匹配 - 人类擅长使用小筹码）在你画的五个内部，如果你没找到，然后将其添加到你的五个。
随意从堆叠中挑选袜子，并与你的5 + 1袜子进行比较。随着筹码的增长，它会降低你的表现，但会提高你的赔率。快多了。
随意记下公式，计算你必须抽取多少样本，以获得50％的匹配几率。 IIRC这是一个超几何定律。
我每天早上都这样做，很少需要超过三次抽奖 - 但我有 n 类似的对（大约10对，给予或带走丢失的对） m 形白色袜子。现在你可以估算一堆股票的大小:-)
BTW，我发现每次需要一对袜子时分拣所有袜子的交易成本总和远远少于做一次并绑定袜子。准时工作更好，因为那时你不必绑袜子，并且还有一个递减的边际收益（也就是说，你继续寻找那两个或三个袜子，当你在洗衣房的某个地方，你需要完成匹配你的袜子，你就失去了时间）。
我所做的就是拿起第一只袜子并将其放下（比如说，放在洗衣盆的边缘）。然后我拿起另一只袜子，检查它是否和第一只袜子一样。如果是，我将它们都删除。如果不是，我把它放在第一个袜子旁边。然后我拿起第三个袜子并将其与前两个比较（如果它们仍在那里）。等等。
假设“删除”袜子是一种选择，这种方法可以相当容易地在数组中实现。 实际上，你甚至不需要“移除”袜子。如果你不需要对袜子进行分类（见下文），那么你可以只是移动它们，最后得到一个阵列，它在阵列中成对排列所有袜子。
假设socks的唯一操作是比较相等，这个算法基本上仍然是n2 算法，虽然我不知道平均情况（从未学会计算）。
排序当然可以提高效率，特别是在现实生活中，您可以轻松地在另外两个袜子之间“插入”袜子。在计算中，同样可以通过树来实现，但这是额外的空间。而且，当然，我们回到NlogN（或者更多，如果有几个袜子通过排序标准相同，但不是来自同一对）。
除此之外，我无法想到任何事情，但这种方法在现实生活中看起来确实非常有效。 :)
这是在问错误的问题。要问的正确问题是，为什么我要花时间整理袜子？当您重视您选择的X货币单位的空闲时间时，每年的成本是多少？
而且往往不仅如此 任何 空闲时间，是的 早上 空闲时间，你可以在床上消费，或喝咖啡，或提前离开，不要被交通堵塞。
退一步往往是好事，并思考解决问题的方法。
还有一种方法！
找一个你喜欢的袜子。考虑所有相关特征：不同光照条件下的颜色，整体质量和耐久性，不同气候条件下的舒适度和气味吸收。同样重要的是，它们不应该在储存时失去弹性，因此天然织物是好的，它们应该用塑料包装。
如果左脚袜和右脚袜之间没有区别，那就更好了，但这并不重要。如果袜子是左右对称的，那么找到一对是O（1）操作，并且对袜子进行排序是近似O（M）操作，其中M是你家里的地方数量，你已经散布着袜子，理想情况下是一些小常数。
如果您选择左右袜子不同的花式配对，则对左右脚桶进行整桶排序需要O（N + M），其中N是袜子的数量，M与上述相同。其他人可以给出寻找第一对的平均迭代的公式，但是找到盲搜索对的最坏情况是N / 2 + 1，这对于合理的N来说变得天文数字不太可能。这可以通过使用高级图像来加速。识别算法和启发式，扫描一堆未分类的袜子 Mk1眼球。
因此，实现O（1）袜子配对效率的算法（假设对称袜子）是：
你需要估计一生中你需要多少双袜子，或者可能直到你退休并转移到温暖的气候而不需要再穿袜子。如果你还年轻，你还可以估计在我们家里都有袜子分拣机器人之前需要多长时间，而整个问题变得无关紧要。
您需要了解如何批量订购您选择的袜子，以及它的成本和交付量。
订购袜子！
摆脱你的旧袜子。
另一个步骤3将涉及比较多年来一次购买相同数量或许更便宜的袜子的成本，并增加分拣袜子的成本，但请相信我的话：批量购买更便宜！此外，存储中的袜子以股票价格通胀的速度增加，这比许多投资所获得的更多。然后还有存储成本，但袜子真的不占用衣柜顶层的空间。
问题解决了。所以，只要得到新的袜子，抛弃/捐赠你的旧袜子，并在知道你每天都在为你的余生节省金钱和时间之后过上幸福的生活。
理论极限是O（n），因为你需要触摸每个袜子（除非一些已经以某种方式配对）。
你可以用O（n）来实现 基数排序。您只需要为存储桶选择一些属性。
如果您可以选择有限数量的属性，但有足够的属性可以唯一地标识每对，那么您应该在O（k * n）中完成，如果我们认为k是有限的，则为O（n）。
作为一个实际解决方案
如果你有1000个袜子，8种颜色和平均分布，你可以在c * n时间内制作每堆125袜子4堆。使用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个元素且具有大约均匀大小的分区的任何等价关系将带来比排序更快的速度提升（假设我们可以直接将袜子分配到其堆中），并且在较小的数据集上可以非常快速地进行排序。
这个问题实际上是深刻的哲学。从本质上讲，人们解决问题的能力（我们大脑的“湿软件”）是否等同于算法可以实现的功能。
一种明显的袜子分类算法是：
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
现在这个问题的计算机科学就是关于步骤的
人类将使用各种策略来实现这些目标。 人类记忆 是 联想，类似于哈希表，其中存储值的特征集与相应的值本身配对。例如，“红色汽车”的概念映射到一个人能够记住的所有红色汽车。拥有完美记忆的人有完美的映射。大多数人在这方面（以及大多数其他人）都不完美。关联映射的容量有限。映射可能 哔 在各种情况下（一个啤酒太多）不存在，被记录错误（“我虽然她的名字是贝蒂，而不是Nettie”），或者永远不会被覆盖，即使我们发现真相已经改变了（“爸爸的车”唤起“橙色火鸟”，当我们真的知道他已交换红色Camaro时）。
在袜子的情况下，完美的召回意味着看着袜子 s 总是产生兄弟姐妹的记忆 t，包括足够的信息（在熨衣板上的位置）来定位 t 在不断的时间。具有照相记忆的人在不变的情况下在恒定时间内完成1和2。
记忆力不够完美的人可能会根据其追踪能力的特征使用一些常识等价类：大小（爸爸，妈妈，宝宝），颜色（绿色，红色等），图案（亚皆老街，平原等） ，风格（footie，knee-high等）。所以熨衣板将分为几类。这通常允许类别按存储器定位在恒定时间内，但是需要通过类别“桶”进行线性搜索。
没有记忆或想象力的人（对不起）只会把袜子放在一堆，并对整堆进行线性搜索。
一个整洁的怪物可能会像有人建议的那样使用数字标签。这为总排序打开了大门，允许人们使用与CPU相同的算法：二进制搜索，树，哈希等。
因此，“最佳”算法取决于运行它的湿件/硬件/软件的质量以及我们通过强制对订单进行“欺骗”的意愿。当然是“最好的” 元 - 算法是雇用世界上最好的袜子分拣机：一个人或机器，可以在1-1联想记忆中获取并快速存储大量的袜子属性集N，具有恒定的时间查找，插入和删除。这样的人和机器都可以采购。如果你有一个，你可以在O（N）时间内将所有袜子配对N对，这是最佳的。总订单标签允许您使用标准散列来获得与人机或硬件计算机相同的结果。
你正试图解决错误的问题。
解决方案1： 每次将脏袜子放入洗衣篮时，请将它们系在一起。这样你洗完后就不用做任何分类了。可以把它想象成在Mongo数据库中注册索引。未来可以节省一些CPU。
解决方案2： 如果是冬天，你不必穿相配的袜子。我们是程序员。只要它有效，没有人需要知道。
解决方案3： 传播工作。您希望异步执行这样一个复杂的CPU进程，而不会阻止UI。把那堆袜子塞进一个袋子里。只在需要时寻找一对。这样，它所需的工作量就不那么明显了。
希望这可以帮助！
这是基于比较的模型的Omega（n log n）下限。 （唯一有效的操作是比较两个袜子。）
假设你 知道 你的2n袜子是这样排列的：
p1 p2 p3 ...... pñ pF（1） pF（2） ...... pF（N）
其中f是集合{1,2，...，n}的未知排列。知道这一点不能使问题更难。有n！可能的输出（第一和第二半之间的匹配），这意味着您需要log（n！）= Omega（n log n）比较。这可以通过分类获得。
由于您对元素清晰度问题的连接感兴趣：证明元素清晰度的Omega（n log n）绑定更难，因为输出是二进制是/否。这里，输出必须是匹配的，并且可能的输出数量足以获得合适的界限。但是，有一个变量连接到元素清晰度。假设你有2n袜子，并想知道它们是否可以独特配对。您可以通过发送（a1， 一个2， ...， 一个ñ）到（a1， 一个1， 一个2， 一个2， ...， 一个ñ， 一个ñ）。 （顺便说一下，ED的硬度证明非常有趣， 通过拓扑。）
我认为应该有一个Omega（n2如果仅允许相等测试，则绑定原始问题。我的直觉是：考虑一个在测试后添加边缘的图形，并认为如果图形不密集，则输出不是唯一确定的。