algorithms leetcode




如何有效地配对袜子? (20)

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

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

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

所以,问题基本上是:

鉴于一堆n双袜子,包含2n元素(假设每个袜子只有一对匹配),有效配对多达对数额外空间的最佳方法是什么? (我相信如果需要,我会记住那些信息。)

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

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

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

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

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

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

希望这可以帮助!


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

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

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

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

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

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

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


为了说明从一堆袜子配对的效率,我们必须首先定义机器,因为配对不是通过图灵也不是通过随机访问机器来完成的,这通常被用作一个基础。算法分析。

机器

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

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

然而,机械物理学给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以立刻移动它们中的一对。

因此,根据以前的分析,操作应按降序使用:

  • 逻辑和算术运算
  • 环境读物
  • 环境修改

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

算法

所以这是我的建议:

  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)),其中rw对于环境的读取和环境写入操作的因素分别为袜子的合理费用。省略了逻辑和算术运算的成本,因为我们假设需要一定量的逻辑和算术运算来决定2个袜子是否属于同一对。这在每种情况下都可能不可行。


作为一个实际解决方案

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

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

与任何c*x*n + O(1)方法相比,该方法将是有利的,大致与log(k) < x - 1一样长。

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

如果我们有多个等价关系,那么该方法也可以嵌套 - >制作颜色堆,而不是在纹理上的每个堆分区内,而不是长度排序。 创建具有大于2个元素且具有大约均匀大小的分区的任何等价关系将带来比排序更快的速度提升(假设我们可以直接将袜子分配到其堆中),并且在较小的数据集上可以非常快速地进行排序。


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

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

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

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

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

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

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

更新:

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

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

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

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

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


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

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

X =你的,Y =你的配偶

从所有袜子的堆A:

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

直到A为空。

对于每一行X和Y.

  1. 选择第一个袜子在线,沿着线搜索,直到找到相应的袜子。

  2. 放入相应的成品袜子。

  3. 可选当您在搜索线条时,您正在查看的当前袜子与之前的袜子相同,请执行这些袜子的步骤2。

可选地,对于第一步,你从那条线而不是两条袜子中拿起两个袜子,因为缓存内存足够大,我们可以快速识别袜子是否与您正在观察的线上的当前袜子匹配。如果你有幸拥有三只手臂,你可以同时解析三只袜子,因为主体的记忆足够大。

直到X和Y都为空。

完成

然而,由于这与选择排序具有类似的复杂性,所以花费的时间远远少于I / O(移动袜子)和搜索(搜索线条的袜子)的速度。


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

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

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

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


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

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

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

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

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


现实世界的方法:

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


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

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

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

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


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

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

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

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

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


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

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

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

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

有两种物理可能性:

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

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

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

然后你所做的就是把你的袜子放在一起,然后把它们放在你的洗衣篮里,然后你再次解决了需要将袜子与“对”概念的物理抽象结合起来的问题。


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

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

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

还有一种方法!

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

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

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

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

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

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

  3. 订购袜子!

  4. 摆脱你的旧袜子。

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

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


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

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


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

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

我是这样做的:

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

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

通过首先拉出独特的袜子,您可以留出空间来“放大”开始时不那么与众不同的特征。

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

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


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

此外,即使是大家庭,我们也不需要承担大量的袜子。袜子被从抽屉中取出并被磨损,并且在被洗涤之前它们被扔在一个地方(可能是垃圾箱)。虽然我不会把所谓的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中,就可以轻松地将所有这些步骤并行化。


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


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

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


这就是我实际操作的方式,对于p双袜子(n = 2p个别袜子):

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

这种方案最糟糕的情况是每双袜子都不同,必须完全匹配,而你挑选的前n / 2袜子都是不同的。这是你的O(n 2)场景,而且不可能。如果袜子t的独特类型的数量小于对的数量p = n / 2,并且每种类型的袜子足够相似(通常与穿着有关的术语),那么任何类型的袜子都可以与任何袜子配对其他的,那么就像我上面推断,你永远不会有比较袜子的最大数量是牛逼,在此之后,下一个你拉的意志匹配其中一个不成对的袜子。这种情况在平均袜子抽屉中比最坏情况更可能发生,并且将最坏情况的复杂性降低到O(n * t),其中通常为t << 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袜子,并想知道它们是否可以独特配对。你可以通过发送从ED的减少(一1,一2,...,一ñ)至(a 1,一1,一2,一2,...,一ñ,一ñ)。 (顺便说一下,ED的硬度证明非常有趣,通过拓扑。)

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







matching