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

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

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

因此,问题基本上是:

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

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

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


当前回答

作为实际解决方案:

快速制作一堆易于区分的袜子。(用颜色表示)快速整理每一堆,并使用袜子的长度进行比较。作为一个人,你可以很快地决定用哪只袜子进行分区,以避免最坏的情况。(你可以看到多只袜子平行排列,这对你有利!)当垃圾堆达到一个阈值时,停止分类,在该阈值下,您可以立即找到不合适的袜子和短袜

如果你有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个以上的元素,且大小大致相等,那么与排序相比,排序的速度都会有所提高(前提是我们可以直接将袜子分配给它的堆),并且排序可以在较小的数据集上快速进行。

其他回答

这是基于比较的模型中的Omega(n log n)下限。(唯一有效的操作是比较两只袜子。)

假设你知道你的2n只袜子是这样排列的:

p1 p2 p3。。。pn pf(1)pf(2)。。。功率因数(n)

其中f是集合{1,2,…,n}的未知排列。知道这一点不会使问题变得更难。有n个!可能的输出(上半部分和下半部分之间的匹配),这意味着您需要log(n!)=Omega(n log n)比较。这可通过分类获得。

由于您对元素区别性问题的连接感兴趣:证明元素区别性的Omega(n log n)界限比较困难,因为输出是二进制的yes/no。这里,输出必须是匹配的,并且可能输出的数量足以获得一个合适的界限。然而,有一个变量与元素的区别有关。假设你有2n只袜子,想知道它们是否可以唯一配对。您可以通过将(a1,a2,…,an)发送到(a1,a1,a2、a2,…、an,an)来获得ED的缩减。(附带地,通过拓扑结构,ED的硬度证明非常有趣。)

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

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

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

将所有袜子放在一张桌子上(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的值!但人们可能会再次反对,因为您可能很难找到(或创建)每只袜子的集群。

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

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

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

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

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

案例1:所有袜子都是一样的(顺便说一句,这是我在现实生活中所做的)。

选择其中的任意两个组成一对。恒定时间。

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

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

情况3:组合的数量事先未知(一般情况)。

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

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

正如许多作者所指出的,基数排序是一种有效的袜子排序方法。尚未提出的是一种完美的哈希方法。用每双袜子买来的时间来计算真是太麻烦了。在你购买袜子时,只需按顺序给袜子编号,就可以让你在整理袜子时把它们放在自己编号的抽屉里。

最多24双袜子的示例。请注意,较大的袜子隔层消除了将袜子卷在一起的需要,这就是所谓的速度/存储权衡。