昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。

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

哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。

因此,问题基本上是:

给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)

我将感谢回答以下方面的问题:

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


当前回答

真实世界方法:

尽快将袜子从未分类的袜子堆中取出,一次一个,然后放在前面。桩应布置得有一定的空间效率,所有袜子指向相同的方向;桩的数量受你容易到达的距离的限制。选择一堆袜子时,应尽快将袜子放在一堆看起来很像的袜子上;偶尔出现的I型(把袜子放在不属于它的袜子堆上)或II型(当有一堆类似的袜子时,把袜子放进自己的袜子堆里)错误是可以容忍的——最重要的考虑是速度。

一旦所有袜子都成了一堆,快速穿过多个袜子堆,创建成对的袜子,然后将它们取下(这些袜子朝抽屉方向)。如果袜子堆中有不匹配的袜子,请将它们重新堆到最好的位置(在尽可能快的限制范围内)。当处理完所有的多袜子堆后,将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦,你完了——我有很多袜子,直到大部分都脏了才洗。另一个实际注意事项是:我将一双袜子的顶部翻转到另一双袜子上,利用它们的弹性财产,以便它们在被运送到抽屉和抽屉中时保持在一起。

其他回答

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

与其他任务合并

我的特殊情况是,我不用烘干机,只是把衣服挂在普通的烘干机上。挂布需要O(n)操作(顺便说一句,我在这里总是考虑垃圾箱包装问题),这个问题本质上需要线性的“额外”空间。当我从桶里拿出一只新袜子时,如果这双袜子已经挂好了,我会试着把它挂在旁边。如果是新袜子,我会在旁边留出一些空间。

Oracle机器更好;-)

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

快到O(n)!

因此,将袜子配对的问题与挂布的问题联系起来,我可以免费获得O(n)“额外的空间”,并有一个及时的解决方案,大约O(n),只需要比简单的挂布多一点的工作,即使在非常糟糕的星期一早晨,也可以立即获得一双完整的袜子…;-)

对于p双袜子(n=2p只袜子),我实际上是这样做的:

从袜子堆里随便拿一只袜子。对于第一只袜子,或者如果之前选择的所有袜子都已配对,只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子,请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时,可以将袜子分为普通类别或类型(白色/黑色、脚踝/圆领、运动型/连衣裙),并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配,把两只袜子放在一起,然后把它们从阵列中去掉。如果没有,请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。

这种方案的最坏情况是,每双袜子都不同,必须完全匹配,而且你挑选的第一双n/2袜子都不同。这是你的O(n2)场景,极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2,并且每种类型的袜子都足够相似(通常在穿着相关的术语中),使得该类型的任何袜子都可以与任何其他袜子配对,那么正如我上面所推断的,你必须与之进行比较的袜子的最大数量是t,之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生,并将最坏情况的复杂性降低到O(n*t),其中通常t<<n。

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

假设看袜子和记住它们独特图案的成本可以忽略不计(ε)。那么最好的解决办法就是把所有的袜子都扔到桌子上。这包括以下步骤:

将所有袜子放在一张桌子上(1),并创建一个hashmap{pattern:position}(ε)当有剩余袜子时(n/2):随机挑选一只袜子(1)查找相应袜子的位置(ε)取回袜子(1)并存放

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

把所有袜子扔在桌子上(1)当有剩余袜子时(n/2):随机挑选一只袜子(1)当未配对时(1/P):找到具有相似图案的袜子拿袜子,比较两者(1)如果可以,存储配对

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

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

对于每只袜子(n):随机挑选一只袜子(1)将其放到其模式的集群中对于每个集群(K):取簇并储存袜子(1+ε)

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

此外,你也可以在网站上查找最佳算法,并提出自己的解决方案,从而节省时间:)

真实世界方法:

尽快将袜子从未分类的袜子堆中取出,一次一个,然后放在前面。桩应布置得有一定的空间效率,所有袜子指向相同的方向;桩的数量受你容易到达的距离的限制。选择一堆袜子时,应尽快将袜子放在一堆看起来很像的袜子上;偶尔出现的I型(把袜子放在不属于它的袜子堆上)或II型(当有一堆类似的袜子时,把袜子放进自己的袜子堆里)错误是可以容忍的——最重要的考虑是速度。

一旦所有袜子都成了一堆,快速穿过多个袜子堆,创建成对的袜子,然后将它们取下(这些袜子朝抽屉方向)。如果袜子堆中有不匹配的袜子,请将它们重新堆到最好的位置(在尽可能快的限制范围内)。当处理完所有的多袜子堆后,将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦,你完了——我有很多袜子,直到大部分都脏了才洗。另一个实际注意事项是:我将一双袜子的顶部翻转到另一双袜子上,利用它们的弹性财产,以便它们在被运送到抽屉和抽屉中时保持在一起。

Defant&Kravitz(1)给出了一种算法,通过将袜子依次放在脚上和脚下来对袜子进行排序。

他们的算法适用于任意数量的英尺。

本文给出了(定理1.1)可使用单脚排序的袜子订单的特征。从他们的定理1.3可以看出,每一个4种颜色的袜子订单最多可以用两只脚进行排序,而有5种颜色的袜订单不可能用两只脚排序。

Colin Defant和Noah Kravitz,袜子足部分类(2022)