已经提出了排序解决方案,但排序有点过多:我们不需要订单; 我们只需要平等团体.

因此散列就足够了(而且速度更快).

1. 对于每种颜色的袜子,形成一堆.迭代输入篮中的所有袜子并将它们分配到颜色堆上.
2. 迭代每一堆并通过一些其他度量(例如模式)将其分配到第二组桩中
3. 递归应用此方案,直到您将所有袜子分布到可以立即直观处理的非常小的桩上

当需要在大型数据集上散列连接或散列聚合时,这种递归散列分区实际上是由SQL Server完成的.它将构建输入流分配到许多独立的分区中.该方案线性地扩展到任意数量的数据和多个CPU.

如果您可以找到提供足够桶的分发键(散列键),并且每个桶足够小以便快速处理,则不需要递归分区.不幸的是,我不认为袜子有这样的属性.

如果每个袜子都有一个名为"PairID"的整数,可以根据PairID % 10(最后一位数)轻松地将它们分配到10个桶中.

我能想到的最好的真实世界分区是创建一个桩的矩形:一个是颜色,另一个是图案.为什么是矩形？因为我们需要O(1)随机访问桩.(3D 长方体也可以使用,但这不太实用.)

更新:

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

1. 最简单的并行化策略是让多个工人从输入篮中取出并将袜子放在桩上.这只能扩大到这么多 - 想象有100人战斗超过10桩.同步成本(表现为手部碰撞和人工通信)会破坏效率和加速(参见通用可扩展性法则!).这容易出现死锁吗？不,因为每个工人一次只需要访问一堆.只有一个"锁定"就不会出现死锁.活锁可能是可能的,取决于人类如何协调对桩的访问.他们可能只是使用像网卡这样的随机退避在物理层面上做这件事以确定哪个卡可以专门访问网络线.如果它适用于NIC,它也适用于人类.
2. 如果每个工人都有自己的一堆桩,它几乎无限地扩展.然后,工人可以从输入篮中取出大块袜子(因为他们很少这样做很少争用)并且在分配袜子时根本不需要同步(因为它们具有线程局部桩).最后,所有工人都需要结合他们的桩.如果工作者形成聚合树,我相信可以在O(log(工人数*每个工人的堆数))中完成.

怎么样的元素明显的问题？正如文章所述,元素清晰度问题可以解决O(N).这对于袜子问题也是一样的(同样O(N),如果你只需要一个分配步骤(我提出了多个步骤只是因为人类在计算上很糟糕 - 如果你分发就一步就足够了md5(color, length, pattern, ...),即所有属性的完美哈希)).

显然,人们不能走得更快O(N),所以我们已达到最佳下限.

虽然输出不完全相同(在一种情况下,只是一个布尔值.在另一种情况下,袜子对),渐近复杂性是相同的.

• 这正是我的所作所为!我根据袜子开口的样式(我只有白色)制作成堆,这给了我足够的"桶"以快速匹配每一个.
• @Nothings不可能这就是哈希冲突攻击对于糟糕的网络服务器的感觉!白袜是否可以通过某种属性区分？必须有一些东西可以分发它们.否则,您可以任意形成对.
• 我上大学的一个人实际上有PairIDs.它被缝在每双袜子上:1号,2号,3号,4号......
• 这是Radix Sort,我同意这是正确的答案.@MarkPeters我认为你不需要查找表.袜子上的单个线性传递可以将袜子转换为数字向量,使得"袜子段"的映射变得简单.袜子可以用绳子绑在矢量上,这样你最后就不需要另一个线性传球了.
• 我用我的袜子尝试了这个(我很容易就有30多对)而男人则很快.我发现的一个问题是当我没有足够好的哈希算法时(我有很多没有任何模式的白袜子)所以它变得很难.在这种情况下,最佳方式是什么？
• 或者你可以做我做的事情并购买100%相同的袜子,然后你可以保证O(1)时间进行搜索和排序.
• @usr它们是可区分的,但不是快速浏览.与文件散列相比,彩色袜子是100KB文件,白色文件是1GB文件,分析需要更长时间.我在练习中所做的就是使用不同的袜子,因为没有人会注意到它.
• 叹.当你把袜子铺在桌子上时,你实际上并不需要做任何特殊的事情.有良好的照明和良好的视力,你*立即挑选对*.它是完全自动的,我们的大脑并行处理每个袜子的图像,并且还表示具有最高匹配确定性的对.如果表格足够大,您可能需要一些可视扫描目标(例如,从工作台伸出的钉子)来强制执行遍布整个表格的可视扫描模式.这个时间成本与袜子数成正比.
• "你马上挑出对子" - 确实叹了口气.不,它显然不是"即时的",并且大脑的处理时间与袜子的数量非线性地增加......以及在桌子上实际到达随机位置的时间也是如此.实际排序袜子的任何人都知道,如果你使用可以快速到达的数量堆,它会快得多*,并且避免随机访问.
• 我不敢相信你在回答一个关于袜子的问题上能得到 19K 的分数
• @MarkPeters好点.有人可能会争辩说我们正在使用人脑作为一个联想阵列:我们可以立即发现具有特定颜色的合适桩.从这个意义上讲,大脑是并行的硬件机器.
• 对于大量的袜子来说,这可能是解决方案,但是递归打桩可能会有点过分.鉴于每次你试图区分一堆袜子时打桩过程会更加困难,因为人眼/大脑的差异并不是立竿见影的.所以我认为只有一到两轮打桩就足以开始匹配.

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

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

• 随着袜子数量的增加,人类的SIMD变得不比CPU好.
• 你最好希望你有一定数量的袜子,否则你将长期折叠袜子......
• 最好的答案,IMO.虽然将日常问题减少到计算机算法是有趣和聪明的(并且适合于SO),但使用人眼/大脑的分辨能力对于小到约60只袜子来说更有意义.
• @LieRyan如果袜子是均匀分布的,你最终会注意到由于生日悖论而在任何足够小的袜子组中注意到一对(除非你可以将颜色区分为任意精度,我怀疑)因此这里的瓶颈不会是人类的颜色匹配算法,但扩散步骤.
• @ dpc.ucore.info不,因为他们有不同的编织袖口图案,袖口长度,整体长度和黑色阴影(我的妻子可能会伤害我最后一个).
• 我不同意大脑是完全不同的建筑."找到匹配的对"可以是一个不太大的集合的一个操作.相当于在机器缓存中搜索 - 这比RAM查找要快得多,但是你要加载这些袜子首先进入"缓存",因此建议的方法仍然是人类和机器的"O(n ^ 2)".
• @Christian:如果你只有黑袜子,袜子上不会有任何其他袜子吗？;)
• 是的.至少,在你匹配所有易识别的对之后,你留下的数字要小得多.我不认为我有任何实际的配对,所以我倾向于"找到两个看起来与平均随机配对不太相似的袜子".
• @Annan嗯,幸运的是你,因为我不能:)
• 同样,对于足够小的样本,选择排序比合并排序更快
• @KubaOber整体上更简单的解决方案可能是通过WashablePair类的实例替换Sock对象对.有袜子配有内置按钮以实现这一目标,但也有改进传统袜子的解决方案,能够在整个洗涤过程中保持配对.我个人从来没有到处重构我的袜子系列.
• @Christian:我也一样.因此我总是使用"处理它"算法:在这种情况下它是唯一可用的.​​..
• @Christian即使在我的黑色袜子中,我也可以轻松识别长度,图案和色调的差异,以找到匹配的对.它并不像注意我唯一一双亮橙色袜子那么容易,但它仍然很容易.我总是散布我的袜子,使它们并排指向同一个方向,这似乎更容易找到对并配对它们.
• 平面视觉扫描性能存在一些严重的局限性.如果有很多相对独特的对(这里没有纯白色袜子),你很快就会超过人脑的视觉扫描能力.需要更多的大脑注意匹配意味着你不能在你的袜子配对时看电视.其他人提到了找到足够大的平坦表面的实际问题.最后,随着表面区域的增加,当您看到靠近地平线的袜子时,您开始遇到距离和视角问题,并且物理地穿过您的分拣区域.

案例1:所有袜子都是相同的(这就是我在现实生活中所做的事情).

选择其中任意两个来做一对.恒定时间.

案例2:有一定数量的组合(所有权,颜色,大小,纹理等).

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

案例3:预先不知道组合的数量(一般情况).

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

然而在现实生活中,当袜子的数量相对较小(恒定)时,这些理论上最优的算法将不能很好地工作.它可能比顺序搜索花费更多时间,顺序搜索理论上需要二次时间.

• 拥有60双相同的袜子"因为它使配对更容易"的问题在于它给人们的印象是你使用计算机.
• 拥有所有相同袜子的缺点是它们倾向于以不同的速度老化.所以你仍然最终会根据它们的磨损程度来匹配它们.(这比通过模式简单匹配更难)
• **案例1**不是涉及操作的恒定时间,例如将对折叠在一起.在这种情况下,它是具有最小常数因子的线性时间(证明其作为读者的练习).**一个**不可能同时折叠一对和一个装满袜子的桶.但是,它线性扩展.根据Amdahl的定律,它具有无限的加速,忽略了开销.根据古斯塔夫森定律,你可以折叠尽可能多的对,以给予足够的工人(其数量留给读者的练习量)折叠一对,忽略开销.
• >它可能比顺序搜索花费更多的时间,这在理论上需要二次时间.是的,这就是为什么我讨厌这样做,也许我应该扔掉所有的袜子,从案例1开始.
• @PauloMadeira排序是恒定的时间 - 你只需把它堆放在你的抽屉里.在这种情况下唯一的操作实际上是将袜子放在你的脚上,这也是不变的.通过延迟执行袜子穿着获得性能,可能在空间中有一些牺牲(非折叠袜子的消耗空间大于折叠).我认为这是值得的; 我和妻子经常失去这种说法.
• 我发现拥有所有相同的袜子也更容易.每隔几年我就会在售卖的时候买6包这些袜子中的10只,扔掉所有旧袜子.更容易匹配相同的袜子,他们看起来比旧的圣袜更好.有了这个,只需一个简单的第一个顶部的桩对我来说是最快的.
• @TerryLi案例4:你有同样的袜子,你的妻子有很多不同的袜子.解决方案:制作2个桩,使用"案例1"作为你的袜子堆,让你的妻子处理她自己的烂摊子.这基本上就是我这样做的:-)

非算法的答案,但当我这样做时"高效":

有时候,我必须再次这样做(丢失袜子,损坏的袜子等),我不喜欢经常丢弃完美好的袜子(我希望他们继续销售相同的袜子参考!),所以我最近采取了一种不同的方法.

算法答案:

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

• 所以随机拿起其中的五个,并记住它们的形状或长度.

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

随意记下公式,计算你必须抽取多少样品,以获得50%的比赛几率.IIRC这是一个超几何定律.

我每天早上这样做,很少需要超过三次抽签 - 但我有n类似的对(大约10对,给予或拿走丢失的)m塑造的白色袜子.现在你可以估算一堆股票的大小:-)

顺便说一句,我发现每次需要一双袜子时,所有袜子的分拣交易成本总和远远低于做一次袜子和绑袜子.准时工作更好,因为你不必绑定袜子,并且还有一个递减的边际收益(也就是说,你一直在寻找那两个或三个袜子,当你在洗衣房的某个地方,你需要完成匹配你的袜子,你就失去了时间).

• Upvote为'非算法'答案.这正是我所做的,它运作得非常好.如果你通过将洗过的袜子放在后面并在早上从抽屉前面拉出来"旋转"你的袜子,那么更换问题不是问题.所有袜子均匀穿着.当我开始注意到一些人的穿着时,我把购物清单上的东西完全取代了整个袜子.对于旧袜子,我给予Goodwill最好的20%(绑在一个杂货囊中,这样他们就不会混合在一起)并推销其余的袜子.你不是在浪费袜子,在这一点上,80%只剩下6个月了.
• 顺便说一句（1）绑定你的袜子会导致弹性袜子被拉伸，并且会更快地失效。限制你所拥有的独特袜子的种类，就不需要绑定了。(2) 限制独特袜子的一个缺点是，对于有一定时尚顾虑的人来说，这种方法可能不合适。
• 我来这里专门发布你的"非算法"答案.与真正的计算机科学一样,大多数人从不对数据及其结构给予足够的重视.
• «n包白色和m包黑色.在日常生活中不需要其他颜色»选择简单袜子的一个好标准规则实际上是它们应该与裤子的颜色或腰带的颜色相匹配.出于这个原因,最常用的颜色可能是黑色,蓝色,灰色和一些棕色.人们很难相信需要很多白袜子.

我做的是拿起第一只袜子并放下(比如在洗衣盆的边缘).然后我拿起另一只袜子检查它是否和第一只袜子一样.如果是,我将它们都删除.如果不是,我把它放在第一只袜子旁边.然后我拿起第三个袜子并将其与前两个比较(如果它们仍在那里).等等.

这种方法可以很容易地在一个数组中实现,假设"删除"袜子是一种选择.实际上,你甚至不需要"移除"袜子.如果你不需要对袜子进行分类(见下文),那么你可以只是移动它们,最后得到一个阵列,它在阵列中成对排列所有袜子.

假设socks的唯一操作是比较相等,这个算法基本上仍然是一个n ²算法,虽然我不知道平均情况(从未学会计算).

排序当然可以提高效率,特别是在现实生活中,您可以轻松地在另外两个袜子之间"插入"袜子.在计算中,可以通过树来实现,但这是额外的空间.当然,我们回到NlogN(或者更多,如果有几个袜子通过排序标准是相同的,但不是来自同一对).

除此之外,我想不出任何东西,但这种方法在现实生活中看起来确实非常有效.:)

• 理论上大量的**类型的**袜子很难缩放
• 这也是我的工作,(请注意,如果你只是留下空格,那么插入也是O(1)),但它与理论上大量的袜子相比很差.
• 在另外两只袜子之间插入袜子有什么价值可以达到配对袜子的目的？袜子没有基数.:-X

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

通常情况下,这不仅仅是任何空闲时间,也就是早上的空闲时间,你可以在床上消费,或者喝着咖啡,或者早点离开并且不会被交通堵塞.

退一步往往是好事,并思考解决问题的方法.

还有一种方法!

找一个你喜欢的袜子.考虑所有相关特征:不同光照条件下的颜色,整体质量和耐久性,不同气候条件下的舒适度和气味吸收.同样重要的是,它们不应该在储存时失去弹性,因此天然织物是好的,它们应该用塑料包装.

如果左脚袜和右脚袜之间没有区别,那就更好了,但这并不重要.如果袜子是左右对称的,找到一对就是O(1)操作,并且对袜子进行分类是近似O(M)操作,其中M是你家里的地方数量,你已经堆满了袜子,理想情况下是一些小常数.

如果您选择左右袜子不同的花式配对,则对左右脚斗进行完整的铲斗排序需要O(N + M),其中N是袜子的数量,M与上面的相同.其他人可以给出寻找第一对的平均迭代的公式,但是找到盲搜索对的最坏情况是N/2 + 1,这对于合理的N来说变得天文不太可能.这可以通过使用高级图像来加速.识别算法和启发式,用Mk1眼球扫描一堆未分类的袜子.

因此,实现O(1)袜子配对效率(假设对称袜子)的算法是:

另一个步骤3将涉及比较多年来一次购买相同数量或许更便宜的袜子的成本,并增加分拣袜子的成本,但请相信我的话:批量购买更便宜!此外,存储中的袜子以股票价格通胀的速度增加,这比许多投资所获得的更多.然后还有存储成本,但袜子真的不占用衣柜顶层的空间.

问题解决了.所以,只要得到新的袜子,抛弃/捐赠你的旧袜子,并在知道你每天都在为你的余生节省金钱和时间之后幸福地生活.

• @AJMansfield 有效的关注。但是，我不同意您的一些数字。我只需要 40 年（25...65 年）的时间（不住在父母/宿舍/等和退休之间的时间，见上文）。另外，我认为一对在原始包装中需要更像是 0,5x4x6 英寸。这些数字使您的空间消耗减少了很多！
• 为可能对 AJMansfield 的测量结果感到困惑的其他人提供指南，将其转换为公制：»将占用（假设一双新袜子占用 327 立方厘米）总共 1.14 立方米。这是一个巨大的空间。假设他们把它装在一个大约是立方体的盒子里交付给你，那么这个板条箱的边长约为 1.04 m。«

理论极限是O(n),因为你需要触摸每个袜子(除非有些已经以某种方式配对).

您可以使用基数排序实现O(n).您只需要为存储桶选择一些属性.

1. 首先你可以选择(她的,我的) - 将它们分成2堆,
2. 然后使用颜色(可以对颜色有任何顺序,例如按颜色名称按字母顺序排列) - 按颜色将它们分成堆(请记住保持同一堆中所有袜子的第1步的初始顺序),
3. 然后袜子的长度,
4. 然后纹理,....

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

• @ Vilx-为什么？!？难道他们无法区分这一点吗？
• 我不同意O(n)的计算.什么是$ k $？$ k $是属性的数量.我认为$ k $是$ O(log n)$因为它必须足以唯一地识别每一对.如果你有2对(黑色和白色),那么颜色($ k = 1,n = 2 $)就足够了.如果你有一双黑色,短; 一双黑色,长; 一对白色,短; 和一对白色,长 - 然后$ k = 2,n = 4 $.然后,如果我们限制$ k $,我们同时限制$ n $.如果我们要限制$ n $那么订单计算就没有意义了.
• 袜子通常是4件装和更大的,因为它更便宜,但这也使它们难以区分.为了解决这个问题,我的妻子在我买的每双新袜子上缝了一个小标记.如果标记用完了颜色,则每个标记的颜色不同,或者颜色不同.使用这种方法,您甚至不需要一组有限的属性.只需在每对上缝上一个唯一的编号.:)对于额外的积分,使用二进制.
• @emory,我认为你正在寻找反引号,而不是`$`字符,让你的东西看起来像代码.
• @flup - 我认为重点是以更大的捆绑销售.:)至于我,这有助于将它们成对磨损.否则我最终会得到三个非常破旧的袜子和一个全新的袜子.有点傻.

作为一个实际解决方案

1. 快速制作成堆易于辨别的袜子.(用颜色说)
2. 每次打桩并使用袜子的长度进行比较.作为一个人,你可以做出一个相当快速的决定,用于分区,避免最坏的情况.(您可以并行查看多个袜子,使用它对您有利!)
3. 当它们达到您可以立即找到现货对和无法使用的袜子的门槛时,停止分拣堆

如果你有1000个袜子,8种颜色和平均分布,你可以在c*n时间内制作每堆125个袜子4堆.阈值为5个袜子,您可以在6次运行中对每一堆进行排序.(计算2秒钟在右侧桩上扔袜子,这将花费你不到4小时.)

如果你只有60只袜子,3种颜色和2种袜子(你/你的妻子),你可以在1次运行中对每堆10只袜子进行分类(再次阈值= 5).(计算2秒钟将需要2分钟).

最初的铲斗分拣会加快你的过程,因为它会及时将你的袜子分成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个元素的分区的任何等价关系将带来比排序更快的速度提升(假设我们可以直接将袜子分配到其堆中),并且在较小的数据集上可以非常快速地进行排序.

• 人类优化:我认为作为人类,对于第2步,你应该按照大致的升序顺序排列袜子,然后以更精细更细的粒度重复,直到排序,有点像shell排序.对于人类(视觉估计)而言,这比基于比较交换的方法快得多.

你正试图解决错误的问题.

解决方案1:每次将脏袜子放入洗衣篮时,请将它们系在一起.这样你洗完后就不用做任何分类了.可以把它想象成在Mongo数据库中注册索引.未来可以节省一些CPU.

解决方案2:如果是冬天,你不必穿袜子.我们是程序员.只要它有效,没有人需要知道.

解决方案3:传播工作.您希望异步执行这样一个复杂的CPU进程,而不会阻止UI.把那堆袜子塞进一个袋子里.只在需要时寻找一对.这样,它所需的工作量就不那么明显了.

希望这可以帮助!

• 将袜子(或任何衣服)系在一起会降低洗衣机洗衣服的能力,并使得解开衣服的难度更大.解决方案2使事态进展的时间越长,维护越困难; 6个月后,当你需要两条黑色及踝袜搭配一双短裤和运动鞋时,6个月做任何工作都会使得在相同条件下(脏/干净,类似的穿着)的发现更不容易.解决方案3不那么"异步",更直接"懒惰"; 在您需要时完成您所需的最低限度的工作.

这个问题实际上是深刻的哲学.从本质上讲,人们解决问题的能力(我们大脑的"湿软件")是否等同于算法可以实现的功能.

一种明显的袜子分类算法是:

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

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

1. "如果s与袜子在N中配对".我们能够多快"记住"到目前为止我们所见过的东西？
2. "从N中删除t"和"将s添加到N".跟踪到目前为止我们看到的东西有多贵？

人类将使用各种策略来实现这些目标.人类记忆是关联的,类似于哈希表,其中存储值的特征集与相应的值本身配对.例如,"红色汽车"的概念映射到一个人能够记住的所有红色汽车.拥有完美记忆的人有完美的映射.大多数人在这方面(以及大多数其他人)都不完美.关联映射的容量有限.在各种情况下(一个啤酒太多),映射可能会黯然失色,被记录错误("我虽然她的名字是Betty,而不是Nettie"),或者即使我们发现真相已经改变,也不会被覆盖("爸爸的汽车"唤起"橙色火鸟"当我们真正知道他已交换红色Camaro时".

在袜子的情况下,完美的回忆意味着看着袜子s总能产生其兄弟的记忆t,包括足够的信息(在熨衣板上的位置)以便t在恒定时间内定位.具有照相记忆的人在不变的情况下在恒定时间内完成1和2.

记忆力不够完美的人可能会根据其追踪能力的特征使用一些常识等价类:大小(爸爸,妈妈,宝宝),颜色(绿色,红色等),图案(亚皆老街,平原等) ,风格(footie,knee-high等).因此,熨衣板将分为几个类别.这通常允许按存储器将类别定位在恒定时间内,但是需要通过类别"桶"进行线性搜索.

没有记忆或想象力的人(对不起)只会把袜子放在一堆,并对整堆进行线性搜索.

一个整洁的怪人可能会像有人建议的那样使用数字标签.这为总排序打开了大门,允许人们使用与CPU相同的算法:二进制搜索,树,哈希等.

因此,"最佳"算法取决于运行它的湿件/硬件/软件的质量以及我们通过对成对订购总订单来"欺骗"的意愿.当然,一个"最好的" 元算法是雇用世界上最好的袜子分类器:一个人或机器,可以在一个1-1的联想记忆中获取并快速存储大量的袜子属性集N,并且具有恒定的时间查找,插入,并删除.这样的人和机器都可以采购.如果你有一个,你可以在O(N)时间内为N对配对所有袜子,这是最佳的.总订单标签允许您使用标准散列来获得与人机或硬件计算机相同的结果.

成本:移动袜子 - >高,找到/搜索袜子 - >小

我们想要做的是减少移动次数,并根据搜索次数进行补偿.此外,我们可以利用智人的多线程环境在决策缓存中保存更多内容.

X =你的,Y =你的配偶

从所有袜子的堆A:

选择两个袜子,在X线上放置相应的X袜子,在下一个可用位置Y袜子放在Y线上.

直到A为空.

对于每一行X和Y.

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 _n)到(a ₁,a ₁,a ₂,a ₂,...,a _n,a _n)来减少ED .(顺便说一下,ED的硬度证明非常有趣,通过拓扑结构.)

我认为如果你只允许相等的测试,应该有一个Omega(n ²)绑定原始问题.我的直觉是:考虑一个在测试后添加边缘的图形,并且认为如果图形不密集,则输出不是唯一确定的.

我就是这样做的,对于p双袜子(n = 2p个别袜子):

• 从堆里随意拿一个袜子.
• 对于第一个袜子,或者如果所有先前选择的袜子已配对,只需将袜子放入您面前的未成对袜子"阵列"的第一个"槽"中.
• 如果您有一个或多个选定的未配对袜子,请检查您当前的袜子是否与阵列中所有未配对的袜子有关.
  • 在构建阵列时,可以将袜子分成一般类别或类型(白色/黑色,脚踝/工作人员,运动/服饰),并"向下钻取"以仅比较相似的类似.
  • 如果找到可接受的匹配项,请将两个袜子放在一起并从阵列中删除它们.
  • 如果不这样做,请将当前袜子放入阵列中的第一个打开的槽中.
• 每个袜子都重复一遍.

这个方案最糟糕的情况是每双袜子都不同,必须完全匹配,你挑选的前n/2袜子都是不同的.这是你的O(n ²)场景,而且极不可能.如果袜子t的独特类型的数量小于对的数量p = n/2,并且每种类型的袜子足够相似(通常与穿着相关的术语),那么任何类型的袜子都可以与任何袜子配对另外,正如我在上面推断的那样,你需要比较的袜子的最大数量是t,之后你拉的下一个袜子将匹配其中一个未配对的袜子.这种情况在平均袜子抽屉中比最坏情况更可能发生,并且将最坏情况的复杂性降低到O(n*t),其中通常为t << n.

现实世界的方法:

尽快将袜子从未分类的绒毛上取下,然后放在你面前的绒毛中.桩应安排在一定程度上空间有效,所有袜子指向相同的方向; 桩的数量受到您可以轻松到达的距离的限制.选择要放袜子的绒毛应该 - 尽快 - 将袜子放在一堆明显像袜子上; 偶尔的I型(将袜子放在它不属于的桩上)或II型(当有现成的袜子堆时,将袜子放在自己的桩中)可以容忍错误 - 最重要的考虑因素是速度.一旦所有袜子成堆,快速穿过多袜子堆创建成对并移除它们(这些正朝向抽屉).如果堆中存在不匹配的袜子,则将它们重新堆放到最佳状态(在尽可能快的约束范围内)堆中.当所有多袜子堆已经处理完毕时,匹配由于II型错误而未配对的剩余可配对袜子.哎呀,你已经完成了 - 我有很多袜子,直到很大一部分脏了才洗它们.另一个实用的注意事项:我将一双袜子的顶部翻过另一个,利用它们的弹性,使它们在被运送到抽屉和抽屉时保持在一起.

从你的问题很清楚,你没有太多实际的洗衣经验:).您需要一种适用于少量不可配对袜子的算法.

到目前为止,答案并未充分利用我们的人类模式识别能力.Set的游戏提供了如何做到这一点的线索:将所有袜子放在一个二维空间中,这样你就可以很好地识别它们,并用手轻松触及它们.这限制了你约120*80厘米左右的面积.从那里选择您识别的对并删除它们.将额外的袜子放在自由空间并重复.如果你为那些容易辨认的袜子(想念小孩子)洗手,你可以先选择那些袜子进行基数分类.该算法仅在单袜数较少时才有效

拿起第一只袜子放在桌子上.现在选另一只袜子; 如果它与第一个选中的相匹配,则将其放在第一个上面.如果没有,请将它放在离第一个小距离的桌子上.选第三个袜子; 如果它匹配前两个中的任何一个,将它放在它们之上,或者将它放在距离第三个小的距离.重复,直到你拿起所有的袜子.

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. 忘记"索引"
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因素.逻辑算术和算术运算的成本被省略,因为我们假设需要一定量的逻辑和算术运算来决定2个袜子是否属于同一对.这在每种情况下都可能不可行.

当我对袜子进行分类时,我会做一个近似的基数排序,将袜子放在其他相同颜色/图案类型的袜子附近.除非我能看到在该位置/附近的完全匹配,我即将放下袜子,我在那时提取该对.

几乎所有其他算法(包括usr的最高得分答案)排序,然后删除对.我发现,作为一个人,最好尽量减少一次考虑的袜子数量.

我是这样做的:

1. 挑选一条与众不同的袜子(无论什么东西都先抓住我的眼睛).
2. 从该概念位置开始基数排序,通过根据与那个的相似性从堆中拉出袜子.
3. 将新袜子放置在当前堆中,距离基于它的不同程度.如果你发现自己把袜子放在另一个上面,因为它是相同的,在那里形成一对,并将它们移除.这意味着未来的比较将花费更少的精力来找到正确的位置.

这利用了人类在O(1)时间内模糊匹配的能力,这在某种程度上等同于在计算设备上建立散列映射.

通过首先拉出独特的袜子,您可以留出空间来"放大"一些不那么与众不同的特征.

在消除了fluro彩色,带有条纹的袜子和三双长袜之后,你可能最终会得到大多数白色袜子,大致按它们的磨损程度排序.

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

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

这也意味着你几乎肯定不会在阵列中拥有所有的袜子,因为袜子会在匹配时被移除.

• @Pykler - 在最好的情况下是O(n),在最坏的情况下是O(n*n).
• 多数民众承认,你不能在你已经看过的所有袜子的头脑中创建一个完全独特的哈希,对我来说,这是一个O(1)来匹配我已经看到过的袜子,并放在等待匹配*哈希*

袜子,无论是真实的袜子还是一些类似的数据结构,都将成对供应.

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

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

将相同的想法应用于配对袜子的实际问题,明显的答案是:不要让你的袜子不配对.袜子作为一对提供,作为一对放入抽屉(也许通过将它们一起打磨),作为一对穿着.但是,可以在洗衣机中取消配对,所以所需要的只是一种物理机制,可以让袜子保持在一起并有效地洗涤.

有两种物理可能性:

对于保持指向每个袜子的指针的"对"对象,我们可以使用一个布袋来保持袜子在一起.这似乎是巨大的开销.

但是对于每个袜子来保持对另一个的引用,有一个简洁的解决方案:一个popper(或者如果你是美国人的'按钮'),例如:

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

然后你所做的就是把它们脱掉并将它们放入洗衣篮后立即将袜子放在一起,然后你再次解决了需要将袜子与"对"概念的物理抽象配对的问题.

考虑大小为"N"的哈希表.

如果我们假设正态分布,那么至少有一个袜子映射到一个桶的"插入"的估计数量是NlogN(即,所有桶都已满)

我把它作为另一个谜题的一部分,但我很高兴被证明是错的.
这是我的博客文章

设'N'对应于您拥有的独特颜色数量/袜子数量的近似上限.

一旦发生碰撞(又名:匹配),只需取下那双袜子即可.对下一批NlogN袜子重复相同的实验.它的美妙之处在于你可以通过人类思维的运作方式进行NlogN并行比较(碰撞解决).:-)

我已经采取了简单的步骤来减少我花费O(1)时间的过程.

通过减少我对两种袜子中的一种(白色袜子用于娱乐,黑色袜子用于工作)的投入,我只需要确定我手中的两个袜子中的哪一个.(从技术上讲,因为它们永远不会一起洗,所以我将过程缩短为O(0)时间)

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

在非常流行和有效的代码中已经多次看到过这种前期努力.例子包括#define'pi到几个小数(其他例子存在,但那是现在想到的那个).

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

• 选择其中一个袜子并将其丢弃(为该对创建一个'桶')
• 如果下一个是前一个对,则将其放入现有存储桶,否则创建一个新存储桶.

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

它不是那么科学,但它运作良好:)

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

此外,即使是大家庭,我们也不需要承担大量的袜子.袜子从抽屉中取出并被磨损,然后将它们扔在一个地方(可能是一个垃圾箱),在洗涤之前它们停留在那里.虽然我不会把所谓的bin称为LIFO-Stack,但我认为这是可以安全的

1. 人们将他们的袜子大致扔在垃圾桶的同一区域,
2. bin在任何时候都不是随机的,因此
3. 从这个箱子的顶部取出的任何子集通常都包含一对袜子.

由于我所知道的所有洗衣机的尺寸都有限(无论你需要洗多少袜子),洗衣机实际随机化,无论我们有多少袜子,我们总是有小的子集,几乎没有单身.

我们的两个预处理阶段是"将袜子放在晾衣绳上"和"从晾衣绳上取袜子",我们必须这样做,以便获得不仅干净而且干燥的袜子.和洗衣机一样,晾衣绳是有限的,我认为我们拥有整条线,我们可以看到袜子.

这是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堆栈,一个有限的普通洗衣机和一个有限的正常晾衣绳 - 但这仍适用于非常大量的袜子.

关于并行性:只要将两个袜子放入同一个bin中,就可以轻松地将所有这些步骤并行化.

如果"移动"操作相当昂贵,并且"比较"操作很便宜,并且您需要将整个集合移动到缓冲区中,其中搜索比原始存储快得多...只需将排序集成到强制中移动.

我发现将分拣过程整合到悬挂干燥使其变得轻而易举.无论如何我需要拿起每个袜子,然后把它挂起来(移动),把它挂在琴弦上的特定位置没什么代价.现在只是不强制搜索整个缓冲区(字符串)我选择按颜色/阴影放置袜子.更深的左,更亮的右边,更多彩的前面等等.现在,在我挂下每个袜子之前,如果已经有匹配的那个,我会看到它的"正确的附近" - 这限制了"扫描"到2-3个其他袜子 - 如果它是,我把另一个挂在它旁边.然后我将它们成对成对,同时在干燥时从琴弦中取出.

现在这可能与顶部答案提出的"按颜色形成桩"有所不同,但首先,通过不选择离散桩而是范围,我可以分类"紫色"是否变为"红色"或"蓝色"堆; 它介于两者之间.然后通过集成两个操作(挂起和排序),挂起的排序开销就像单独排序的10%.

我的解决方案并不完全符合您的要求,因为它正式需要O(n)"额外"空间.但是,考虑到我的条件,它在我的实际应用中非常有效.因此,我认为它应该是有趣的.

结合其他任务

我的特殊情况是我不使用烘干机,只需将布挂在普通的布烘干机上.挂布需要O(n)操作(顺便说一下,我总是考虑这里的装箱问题),问题本质上需要线性的"额外"空间.当我从桶中取出一个新的袜子时,我试着把它挂在它的一对旁边,如果它已经挂了.如果它是一对新袜子,我会留下一些空间.

Oracle机器更好;-)

显然需要一些额外的工作来检查是否有匹配的袜子已经挂在某处,它将为计算机O(n^2)提供系数的解决方案1/2.但在这种情况下,"人为因素"实际上是一个优势 - 我通常可以很快(几乎O(1))识别匹配的袜子,如果它已经挂起(可能涉及一些难以察觉的脑内缓存) - 认为它是一种Oracle机器中有限的"oracle" ;-)我们在某些情况下人类比数字机器具有这些优势;-)

几乎拥有它O(n)!

因此,将袜子配对的问题与挂布的问题联系起来我O(n)免费获得"额外空间",并且有一个O(n)及时的解决方案,只需要比简单的挂布更多的工作,并允许立即访问完整的一对袜子甚至在一个非常糟糕的星期一早上... 😉

做一些预处理怎么样？我会在每个袜子上缝上一个标记或id号码,每一对都有相同的标记/ id号码.每次购买一双新袜子时都可以完成这个过程.然后,您可以进行基数排序以获得O(n)总成本.找到每个标记/身份证号码的位置,然后逐个挑选所有袜子并将它们放入正确的位置.

使用模式作为哈希,创建一个将用于不匹配的socks的哈希表.逐个迭代袜子.如果袜子在哈希表中具有模式匹配,则将袜子从表中取出并成对.如果袜子没有匹配,请将其放入表中.

排序你的n双袜子的问题是O(n).在将它们扔进洗衣篮之前,先将左边的一个穿到右边的一个.取出它们后,你切断了线程并将每一对放入你的抽屉 - 在n对上进行2次操作,所以O(n).

现在接下来的问题就是你是否自己洗衣服,而你的妻子是自己洗衣服.这可能是一个完全不同的问题领域的问题.:)

我在博士(计算机科学)期间经常考虑这个问题.我提出了多种解决方案,具体取决于区分袜子的能力,从而尽可能快地找到正确的对.

假设看袜子和记忆他们的独特模式的成本可以忽略不计(ε).然后最好的解决方案是将所有袜子扔在桌子上.这包括以下步骤:

1. 将所有袜子扔在桌子上(1)并创建一个hashmap {pattern:position}(ε)
2. 虽然有剩余袜子(n/2):
   1. 拿一个随机袜子(1)
   2. 找到相应袜子的位置(ε)
   3. 检索袜子(1)和商店对

这确实是最快的可能性,并且以n + 1 = O(n)复杂度执行.但它假设您完全记住所有模式......在实践中,情况并非如此,我个人的经验是您有时在第一次尝试时找不到匹配对:

1. 把所有的袜子扔在桌子上(1)
2. 虽然有剩余袜子(n/2):
   1. 拿一个随机袜子(1)
   2. 虽然没有配对(1/P):
      1. 找到类似图案的袜子
      2. 拿袜子比较两者(1)
      3. 如果可以的话,存储对

这现在取决于我们找到匹配对的能力.如果您有深色/灰色对或白色运动袜通常具有非常相似的图案,则尤其如此!让我们承认你有P找到相应袜子的概率.在找到相应的袜子形成一对之前,你平均需要1/P次尝试.总体复杂度为1 +(n/2)*(1 + 1/P)= O(n).

两者都是袜子数量的线性,是非常相似的解决方案.让我们稍微修改一下这个问题并承认你在套装中有多对类似的袜子,并且很容易在一次移动中存储多对袜子(1 +ε).对于K个不同的模式,您可以实现:

1. 对于每个袜子(n):
   1. 拿一个随机袜子(1)
   2. 把它放在它的模式集群上
2. 对于每个群集(K):
   1. 采取集群和存储袜子(1 +ε)

总体复杂度变为n + K = O(n).它仍然是线性的,但选择正确的算法现在可能在很大程度上取决于P和K的值!但有人可能会再次反对您可能难以为每个袜子找到(或创建)簇.

此外,您还可以通过在网站上查看最佳算法并提出自己的解决方案来节省时间:)

从一堆袜子配对的有效算法

先决条件

1. 堆里必须至少有一只袜子
2. 桌子必须足够大以容纳 N/2 只袜子（最坏的情况），其中 N 是袜子的总数。

算法

尝试：

1. 选择第一只袜子
2. 把它放在桌子上
3. 选择下一只袜子，然后看看它（可能会抛出“堆里没有更多的袜子”异常）
4. 现在扫描桌子上的袜子（如果桌子上没有袜子，则抛出异常）
5. 有比赛吗？a) 是 => 从桌子上移除匹配的袜子 b) 否 => 把袜子放在桌子上（可能会抛出“桌子不够大”异常）

除了：

最后：

• 如果堆里还有袜子：
  
     转到3

已知的问题

如果周围没有桌子或桌子上没有足够的地方容纳至少一只袜子，算法将进入无限循环。

可能的改进

根据要分类的袜子数量，如果有足够的空间，可以通过对桌子上的袜子进行分类来增加吞吐量。

为了使其起作用，需要一个属性，该属性对于每双袜子都具有唯一值。这种属性可以很容易地从袜子的视觉特性中合成。

按所述属性对桌子上的袜子进行排序。让我们称该属性为“颜色”。把袜子排成一排，把深色的袜子放在右边（即.push_back()），把浅色的袜子放在左边（即.push_front()）

对于巨大的堆，尤其是以前看不见的袜子，属性合成可能需要大量时间，因此吞吐量会明显下降。但是，这些属性可以保留在内存中并重复使用。

需要进行一些研究来评估这种可能改进的效率。出现以下问题：

• 使用上述改进配对的最佳袜子数量是多少？
• 对于给定数量的袜子，在吞吐量增加之前需要进行多少次迭代？
  
  a) 对于最后一次迭代
  
  b) 对于所有迭代整体

符合MCVE指南的PoC ：

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