题 如何有效地配对袜子?


昨天我把干净的洗衣店的袜子配对,弄清楚我做的方式效率不高。我正在做一个天真的搜索 - 挑选一个袜子并“迭代”堆,以找到它的对。这需要迭代n / 2 * n / 4 = n2/平均8个袜子。

作为一名计算机科学家,我在想我能做些什么?当然,为了实现O(NlogN)解决方案,我们会想到排序(根据大小/颜色/ ...)。

哈希或其他非就地解决方案不是一种选择,因为我无法复制我的袜子(尽管如果可能的话可能会很好)。

所以,问题基本上是:

给了一堆 n 一双袜子,含有 2n 元素(假设每个袜子只有一个匹配对),有效配对它们的最佳方法是什么? (我相信如果需要,我会记住那些信息。)

我将感谢一个解决以下方面的答案:

  • 一般 理论 大量袜子的解决方案。
  • 袜子的实际数量并不是那么大,我不相信我的配偶和我有超过30双。 (并且很容易区分我的袜子和她的袜子;这也可以使用吗?)
  • 它等同于 元素清晰度问题

3507
2018-01-19 15:34


起源


我使用鸽子孔原理与洗衣堆完全配对。我有3种不同颜色的袜子(红色,蓝色和绿色)和每种颜色2对。我每次拿起4个袜子而且我总是配对并开始工作。 - Srinivas
另一个鸽子洞的原则:如果你拿一部分n / 2 + 1袜子,那里 一定是 该子集中至少有一对。 - wildplasser
好问题!您可能对我关于相关问题的文章感兴趣,该文章讨论了将两个匹配的袜子从堆中拉出的可能性: blogs.msdn.com/b/ericlippert/archive/2010/03/22/... - Eric Lippert
为什么不产生一个孩子和 waitpid 所以,作为父母,你甚至不自己整理任何袜子? - Mxyk
我只拥有白色及膝袜,解决了这个问题。他们都匹配。我可以随便从堆中随意抓住任何两个袜子,他们会匹配。我通过不配对袜子进一步简化了问题。我有一个袜子抽屉,我只是把我所有的袜子扔进去,未配对。我每天早上从抽屉里随意抓两个。我把它简化为O(0)。不能比这更简单。 :) - Lee


答案:


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

所以 散列 就足够了(而且速度更快)。

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

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

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

如果每个袜子都有一个名为“PairID”的整数,那么根据它可以很容易地将它们分配到10个桶中 PairID % 10 (最后一位数字)。

我能想到的最好的真实分区是创建一个 长方形的桩:一个是颜色,另一个是图案。为什么是矩形?因为我们需要O(1)随机访问桩。 (3D 长方体 也会有用,但那不太实用。)


更新:

关于什么 排比?多个人可以更快地匹配袜子吗?

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

关于 元素清晰度问题?正如文章所述,元素清晰度问题可以解决 O(N)。袜子问题也是如此(同样如此) O(N),如果你只需要一个分配步骤(我提出了多个步骤只是因为人类计算不好 - 如果你分发的话,一步就够了 md5(color, length, pattern, ...),即a 完美哈希 所有属性))。

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

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


2180
2017-10-19 20:47



这正是我的所作所为!我根据袜子开口的样式(我只有白色)制作成堆,这给了我足够的“桶”以快速匹配每一个。 - Scott Chamberlain
我用我的袜子尝试了这个(我很容易就有30多对)而男人则很快。我发现的一个问题是当我没有足够好的哈希算法时(我有很多没有任何模式的白袜子)所以它变得很难。在这种情况下,最佳方式是什么? - NothingsImpossible
@Nothings不可能这就是哈希冲突攻击对于糟糕的网络服务器的感觉!白袜是否可以通过某种属性区分?必须有可以分发它们的东西。否则,您可以任意形成对。 - usr
这是Radix Sort,我同意这是正确的答案。 @MarkPeters我认为你不需要查找表。袜子上的单个线性传递可以将袜子转换为数字向量,使得“袜子段”的映射变得简单。袜子可以用绳子绑在矢量上,这样你最后就不需要另一个线性传球了。 - Pointy
我上大学的一个人实际上有PairIDs。它被缝在每双袜子上:1号,2号,3号,4号...... - Ryan Lundy


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

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


523
2018-05-27 19:13



随着袜子数量的增加,人类的SIMD变得不比CPU好。 - Lie Ryan
最好的答案,IMO。虽然将日常问题减少到计算机算法是有趣和聪明的(并且适合于SO),但使用人眼/大脑的分辨能力来设置小到约60个袜子更有意义。 - drug_user841417
@LieRyan如果袜子是均匀分布的,那么由于生日悖论,你最终会注意到任何一套足够小的袜子(除非你能分辨颜色到任意精度,我怀疑),所以这里的瓶颈不会是人体颜色匹配算法但是传播步骤。 - Thomas
@ dpc.ucore.info不,因为他们有不同的编织袖口图案,袖口长度,整体长度和黑色阴影(我的妻子可能会伤害我最后一个)。 - Christian
你最好希望你有一定数量的袜子,否则你将长期折叠袜子...... - Patrick James McDougle


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

选择他们中的任何两个来做一对。恒定时间。

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

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

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

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

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


231



>它可能比顺序搜索花费更多的时间,这在理论上需要二次时间。是的,这就是为什么我讨厌这样做,也许我应该扔掉所有的袜子,从案例1开始。 - Nils
我发现拥有所有相同的袜子也更容易。每隔几年我就会购买6包这些袜子中的10只,然后扔掉我所有的旧袜子。更容易匹配相同的袜子,他们看起来比旧的圣袜更好。有了这个,只需一个简单的首先从堆顶部对我来说是最快的。 - Michael D. Kirkpatrick
拥有所有相同袜子的缺点是它们往往以不同的速度老化。所以你仍然最终会根据它们的磨损程度来匹配它们。 (这比通过模式简单匹配更难) - SDC
拥有60双相同的袜子“因为它使配对更容易”的问题在于它给人的印象是你使用计算机。 - Steve Ives
情况1 当涉及操作时不是恒定的时间,例如将对折叠在一起。在这种情况下,它是具有最小常数因子的线性时间(证明其作为读者的练习)。 一 不可能同时折叠一双和一个装满袜子的桶。但是,它线性扩展。根据Amdahl的定律,它具有无限的加速,忽略了开销。根据古斯塔夫森定律,你可以折叠尽可能多的配对,只要有足够的工人(其数量留给读者的练习)就可以折叠一对,而忽略了开销。 - acelent


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

  • 步骤1)丢弃所有现有的袜子

  • 第2步)去 沃尔玛(Walmart) 并通过10-n包的数据包购买 白色和米包黑色。每天都不需要其他颜色 生活。

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

算法答案:

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

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

为什么五个?通常人类是好的,记住工作记忆中的五到七个不同的元素 - 有点像人类的等同于一个 RPN stack - five是一个安全的默认值。

  • 从2n-5的筹码中挑选一个。

  • 现在寻找一个匹配(视觉模式匹配 - 人类擅长使用小筹码)在你画的五个内部,如果你没找到,然后将其添加到你的五个。

  • 随意从堆叠中挑选袜子,并与你的5 + 1袜子进行比较。随着筹码的增长,它会降低你的表现,但会提高你的赔率。快多了。

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

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

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


144



赞成“非算法”答案。这正是我所做的,它运作得非常好。如果你通过将洗过的袜子放在后面并在早上从抽屉前面拉出来“旋转”你的袜子来替换问题不是问题。所有袜子均匀穿着。当我开始注意到一些穿着时,我把购物清单上的东西完全取代了整个袜子。对于旧袜子,我将最好的20%给予Goodwill(捆绑在杂货囊中,这样他们就不会混入其中)并推销其余的袜子。你不是在浪费袜子,在这一点上,80%只剩下6个月了。 - FastAl
BTW(1)绑定你的袜子导致弹性的一个被拉伸存储,并且会更快地失败。限制你所拥有的独特袜子种类使得绑定不必要。 (2)限制独特袜子的缺点是对于具有某些时尚顾虑的人来说,该方法可能是不合适的。 - FastAl
我来这里专门发布你的“非算法”答案。与真正的计算机科学一样,大多数人从不对数据及其结构给予足够的重视。 - bkconrad
我每天早上都使用这种算法,它就像一个魅力!另外,我把破旧的袜子放到不同的堆中以便稍后丢弃(不幸的是,在我找到时间去垃圾之前,他们设法再次到达原始的堆)。 - Donatas Olsevičius
«n包白色和m包黑色。在日常生活中不需要其他颜色»选择简单袜子的一个好标准规则实际上是它们应该与裤子的颜色或腰带的颜色相匹配。出于这个原因,最常用的颜色可能是黑色,蓝色,灰色和一些棕色。人们很难相信需要很多白袜子。 - Andrea Lazzarotto


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

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

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

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

除此之外,我无法想到任何事情,但这种方法在现实生活中看起来确实非常有效。 :)


92



这也是我的工作,(请注意,如果你只是留下空格,那么插入也是O(1)),但它与理论上大量的袜子相比很差。 - Mooing Duck
理论上大量的 种类 袜子 - Steven Lu
@StevenLu - 正如我所说 - 它是n * n或nLogn,取决于你是否排序。所以它的扩展与任何排序算法一样差。如果你想要更快,请为它们编号并使用基数排序。 - Vilx-
这基本上是在基于散列的查找中存储已找到但未匹配的袜子。理想的哈希是O(n),但是如果你有足够的袜子存储哈希开始退化,那么它就会变得更加复杂。 - Jon Hanna
在另外两只袜子之间插入袜子有什么价值可以达到配对袜子的目的?袜子没有基数。 :-X - JoeBrockhaus


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

而且往往不仅如此 任何 空闲时间,是的 早上 空闲时间,你可以在床上消费,或喝咖啡,或提前离开,不要被交通堵塞。

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

还有一种方法!

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

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

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

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

  1. 你需要估计一生中你需要多少双袜子,或者可能直到你退休并转移到温暖的气候而不需要再穿袜子。如果你还年轻,你还可以估计在我们家里都有袜子分拣机器人之前需要多长时间,而整个问题变得无关紧要。

  2. 您需要了解如何批量订购您选择的袜子,以及它的成本和交付量。

  3. 订购袜子!

  4. 摆脱你的旧袜子。

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

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


50



一生(假设75年)袜子供应(假设你每天减少4对,即3600对)会占用(假设一双袜子占用20立方英寸),总共1 1/2立方码。这是一个巨大的空间。假设他们在一个大致为立方体的盒子里把它递给你,那个箱子一边大约3英尺4英寸。 - AJMansfield
@AJMansfield有效关注。但是,我不同意你的一些数字。我需要花费40年(25 ... 65)的时间(不住在父母/宿舍/等等和退休之间的时间,见上文)。另外,我认为原装包装中的一对更像是0.5x4x6英寸。这些数字可以让你的空间节省很多! - hyde
步骤4不必要地浪费,-1。 - Dan Bechard
对于可能被AJMansfield测量值混淆的其他人的指南,对公制的翻译:»将占用(假设一双袜子需要327cm³),总计1.14m³。这是一个巨大的空间。假设他们在一个大致为立方体的盒子里把它递给你,那个箱子的边长约为1.04米。« - Joey


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

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

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

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


47



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


作为一个实际解决方案

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

如果你有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个元素且具有大约均匀大小的分区的任何等价关系将带来比排序更快的速度提升(假设我们可以直接将袜子分配到其堆中),并且在较小的数据集上可以非常快速地进行排序。


31



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


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

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

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”。跟踪到目前为止我们所见过的东西有多昂贵?

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

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

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

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

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

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


25



好吧,那更好,虽然它仍然是错误的...这个问题与此无关。无论Church-Turing论文是否正确,人类和我们的计算机都可以对袜子进行排序。 (现实情况是,人类作为高度有限的实体,其计算能力远远低于图灵机器......我们的计算机也是如此,但局限性不同。) - Jim Balter
我不同意。当然,我们当前的任何计算机都是基本上和巨大的DFA(模数i / o差异)而不是TM。然而,任何模拟设备,例如我们的身体,都能够模仿无限的磁带。我们还没有对我们的思维方式进行有用的描述。 - Gene
没有人类或其他物理设备的无限磁带,因为人类大脑中没有任何东西具有无限分辨率,也不可能。它也有助于学习一些神经科学。无论如何,这里没有深刻的哲学问题,无论你想注入一个。但是相信你会...这不是这种辩论的地方,而且我之前已经有太多次了。但我总是被那些几乎无法解决最简单问题的人(我们所有人)想象他们都是TM等同的人所逗乐。 - Jim Balter


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

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

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

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

希望这可以帮助!


24



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


这是基于比较的模型的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如果仅允许相等测试,则绑定原始问题。我的直觉是:考虑一个在测试后添加边缘的图形,并认为如果图形不密集,则输出不是唯一确定的。


20