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

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

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

因此,问题基本上是:

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

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

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


当前回答

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

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

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

其他回答

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

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

我将此作为另一个谜题的一部分,但我很乐意被证明是错误的。这是我的博客文章

让“N”对应于袜子独特颜色/图案数量的近似上限。

一旦发生碰撞(也就是火柴),只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于,由于人类思维的方式,你可以进行NlogN并行比较(冲突解决)

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

选择一只袜子并将其收起来(为这双袜子创建一个“水桶”)如果下一个是上一个的一对,则将其放到现有的存储桶中,否则创建一个新的存储桶。

在最坏的情况下,这意味着您将有n/2个不同的存储桶,并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然,如果你只有几对,这个算法会很好地工作;我用了12双鞋。

它不是那么科学,但它工作得很好:)

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

步骤1)丢弃所有现有袜子第2步)去沃尔玛买10-n包的白色和m包黑色。日常无需其他颜色生活

然而,有时,我不得不再次这样做(丢失的袜子、损坏的袜子等),我讨厌太频繁地丢弃完美的袜子(我希望他们继续出售相同的袜子参考!),所以我最近采取了不同的方法。

算法答案:

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

所以,随机挑选其中五个,记住它们的形状或长度。

为什么是五?通常情况下,人类在工作记忆中记住五到七个不同的元素是很好的——有点像RPN堆栈的人类等价物——五个是安全的默认值。

从2n-5的堆栈中选择一个。现在,在你画的五个图案中寻找一个匹配(视觉模式匹配-人类擅长用一个小堆栈),如果你没有找到一个,那么把它添加到你的五个。继续从袜子堆中随机挑选袜子,并与你的5+1袜子进行比较。随着堆栈的增长,它会降低性能,但会提高赔率。快得多。

请随意写下公式,以计算50%的匹配几率需要抽取多少样本。IIRC这是一个超几何定律。

我每天早上都会这样做,很少需要三次以上的平局——但我有n双类似的m形白袜子(大约10双,不分输赢)。现在你可以估计我的股票堆的大小:-)

顺便说一句,我发现,每次我需要一双袜子时,整理所有袜子的交易成本之和远远少于一次整理和装订袜子。准时制的效果更好,因为这样你就不必绑袜子了,而且边际回报也在减少(也就是说,当你在洗衣店的某个地方时,你一直在寻找那两到三只袜子,而你需要完成袜子的搭配,而你却在这上面浪费了时间)。

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

与其他任务合并

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

Oracle机器更好;-)

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

快到O(n)!

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

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

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

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

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