昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家,我在想我能做什么?排序(根据大小/颜色/…)当然是为了实现O(NlogN)解决方案。
哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。
因此,问题基本上是:
给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)
我将感谢回答以下方面的问题:
大量袜子的一般理论解。袜子的实际数量没有那么多,我不相信我的配偶和我有超过30双。(而且很容易区分我的袜子和她的袜子;这也可以用吗?)它是否等同于元素清晰度问题?
这是问错了问题。正确的问题是,我为什么要花时间整理袜子?如果你选择X个货币单位来计算你的空闲时间,那么每年的花费是多少?
通常情况下,这不仅仅是任何空闲时间,这是早晨的空闲时间,你可以躺在床上,或者喝咖啡,或者早点离开,不被交通堵塞。
退一步想办法解决问题通常是好的。
还有一个办法!
找一只你喜欢的袜子。考虑所有相关特征:不同照明条件下的颜色、整体质量和耐久性、不同气候条件下的舒适性以及气味吸收。同样重要的是,它们在储存过程中不应失去弹性,所以天然织物是好的,它们应该可以用塑料包装。
如果左脚和右脚的袜子没有区别,那就更好了,但这并不重要。如果袜子是左右对称的,找到一双袜子是O(1)运算,而对袜子进行排序是近似的O(M)运算,其中M是你家里扔袜子的地方的数量,理想情况下是一个小常数。
如果你选择了一双左右袜子不同的奇装异服,对左脚和右脚的桶进行全桶排序,取O(N+M),其中N是袜子的数量,M与上述相同。其他人可以给出找到第一双袜子的平均迭代次数的公式,但通过盲搜索找到一双袜子的最坏情况是N/2+1,对于合理的N来说,这在天文学上是不太可能的。当用Mk1 Eyeball扫描一堆未分类的袜子时,使用先进的图像识别算法和启发式方法可以加快速度。
因此,实现O(1)袜子配对效率的算法(假设对称袜子)为:
你需要估计你的余生需要多少双袜子,或者直到你退休并搬到更温暖的气候,不再需要穿袜子。如果你还年轻,你还可以估计我们需要多长时间才能在家里拥有袜子分拣机器人,而整个问题变得无关紧要。您需要了解如何批量订购您选择的袜子,以及它的价格,以及它们的送货方式。订购袜子!扔掉你的旧袜子。
另一个步骤3将包括比较几年来一次购买几双同样数量的可能更便宜的袜子的成本,并加上整理袜子的成本。但我要保证:批量购买更便宜!此外,库存袜子的价值会随着股价的上涨而增加,这比你在很多投资中得到的要多。此外,还有存储成本,但袜子确实不会占用壁橱顶部货架上的空间。
问题已解决。所以,只要买一双新袜子,扔掉/捐赠你的旧袜子,在知道你的余生每天都在节省金钱和时间之后,就可以幸福地生活下去。
袜子,无论是真的还是类似的数据结构,都将成对提供。
最简单的答案是,在允许袜子对分开之前,应该初始化袜子对的单个数据结构,该结构包含指向左右袜子的指针,从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。
这通过使用抽象层来消除任何计算配对问题。
将同样的想法应用于袜子配对的实际问题,显而易见的答案是:不要让你的袜子不配对。袜子是一双提供的,一双放在抽屉里(也许是把它们捆在一起),一双穿。但可能脱漆的地方是在洗衣机里,所以所需要的只是一个物理机制,让袜子保持在一起并有效地清洗。
有两种物理可能性:
对于一个“pair”对象,它保持指向每只袜子的指针,我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。
但是,为了让每一只袜子都能互相参照,有一个很好的解决方案:一个popper(如果你是美国人,可以使用“按扣”),比如:
http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html
然后,你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起,再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。
作为实际解决方案:
快速制作一堆易于区分的袜子。(用颜色表示)快速整理每一堆,并使用袜子的长度进行比较。作为一个人,你可以很快地决定用哪只袜子进行分区,以避免最坏的情况。(你可以看到多只袜子平行排列,这对你有利!)当垃圾堆达到一个阈值时,停止分类,在该阈值下,您可以立即找到不合适的袜子和短袜
如果你有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个以上的元素,且大小大致相等,那么与排序相比,排序的速度都会有所提高(前提是我们可以直接将袜子分配给它的堆),并且排序可以在较小的数据集上快速进行。
我所做的就是拿起第一只袜子,把它放下(比如,放在洗衣碗的边缘)。然后我拿起另一只袜子,检查它是否与第一只袜子相同。如果是,我会把它们都去掉。如果不是,我把它放在第一只袜子旁边。然后我拿起第三只袜子,将其与前两只袜子进行比较(如果它们还在的话)。等
这种方法可以很容易地在阵列中实现,假设“移除”袜子是一个选项。实际上,你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序(见下文),那么您只需移动它们,就可以得到一个数组,该数组中所有袜子都成对排列。
假设袜子的唯一操作是比较相等,这个算法基本上仍然是n2算法,尽管我不知道平均情况(从未学会计算)。
当然,分类可以提高效率,尤其是在现实生活中,你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中,树也可以做到这一点,但这是额外的空间。当然,我们又回到了NlogN(或者更多,如果有几只袜子按排序标准是相同的,但不是来自同一双)。
除此之外,我想不出什么,但这种方法在现实生活中似乎非常有效
对于p双袜子(n=2p只袜子),我实际上是这样做的:
从袜子堆里随便拿一只袜子。对于第一只袜子,或者如果之前选择的所有袜子都已配对,只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子,请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时,可以将袜子分为普通类别或类型(白色/黑色、脚踝/圆领、运动型/连衣裙),并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配,把两只袜子放在一起,然后把它们从阵列中去掉。如果没有,请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。
这种方案的最坏情况是,每双袜子都不同,必须完全匹配,而且你挑选的第一双n/2袜子都不同。这是你的O(n2)场景,极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2,并且每种类型的袜子都足够相似(通常在穿着相关的术语中),使得该类型的任何袜子都可以与任何其他袜子配对,那么正如我上面所推断的,你必须与之进行比较的袜子的最大数量是t,之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生,并将最坏情况的复杂性降低到O(n*t),其中通常t<<n。