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

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

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

因此,问题基本上是:

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

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

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


当前回答

从你的问题来看,你显然没有太多洗衣方面的实际经验:)。你需要一种算法,能很好地处理少量不可配对的袜子。

到目前为止,答案还没有充分利用我们的人类模式识别能力。集合游戏提供了如何做好这一点的线索:将所有袜子放在一个二维空间中,这样你就可以很好地识别它们,并用手轻松地够到它们。这将您的面积限制在120*80厘米左右。从那里选择您识别的配对并将其删除。将多余的袜子放在空闲空间,然后重复。如果你为穿着容易辨认的袜子的人洗衣服(脑海中浮现的是小孩子),你可以先选择袜子来进行基数排序。该算法仅在单袜子数量较少时有效

其他回答

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

此外,即使是大家庭,我们也不需要假设有大量袜子。袜子从抽屉中取出并穿上,然后在洗衣服之前,将它们扔到一个地方(可能是一个垃圾箱)。虽然我不会将所说的垃圾箱称为后进先出堆栈,但我认为可以安全地假设

人们把两只袜子大致扔在箱子箱子在任何时候都不会随机化,因此从该容器顶部获取的任何子集通常都包含一双袜子。

由于我所知道的所有洗衣机的尺寸都是有限的(不管你要洗多少袜子),而且洗衣机中会发生实际的随机性,所以无论我们有多少袜子,我们总是有几乎不含单品的小子集。

我们的两个预处理阶段是“把袜子放在晾衣绳上”和“把袜子从晾衣绳里拿出来”,我们必须这样做,这样才能得到既干净又干燥的袜子。和洗衣机一样,晾衣绳是有限的,我假设我们可以看到袜子的整个部分。

以下是put_socks_on_ine()的算法:

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_maining_clusters()的算法:

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

之后,只剩下几只袜子了。在这里,我将之前未配对的袜子引入到系统中,并在不使用任何特殊算法的情况下处理剩余的袜子——剩余的袜子非常少,可以非常快速地进行视觉处理。

对于所有剩余的袜子,我假设它们的同伴仍然没有洗,并将它们放在一边,以备下次迭代。如果你记录了一段时间内未配对袜子的增长(“袜子泄漏”),你应该检查你的垃圾箱——它可能会随机出现(你有猫睡在里面吗?)

我知道这些算法需要很多假设:一个充当某种LIFO堆栈的垃圾箱,一台有限的普通洗衣机,以及一条有限的普通晾衣绳——但这仍然适用于大量袜子。

关于并行性:只要你把两个袜子放在同一个箱子里,你就可以很容易地并行化所有这些步骤。

如果你可以将一双袜子抽象为密钥本身,将另一双袜子作为值,那么我们可以使用哈希来发挥作用。

在你身后的地板上做两个假想的部分,一个给你,另一个给配偶。从袜子堆里取一只。现在,按照以下规则将袜子一只一只地放在地板上。确定袜子是你的还是她的,并查看地板上的相关部分。如果你能在地板上找到这双鞋,就把它捡起来,把它们系起来,或者把它们夹起来,或者在找到一双鞋后做任何你想做的事情,然后把它放在篮子里(把它从地板上取下来)。将其放在相关章节中。重复3次,直到所有袜子都从袜子堆上取下。

说明:

哈希和抽象

抽象是一个非常强大的概念,已用于改善用户体验(UX)。现实生活中与计算机交互的抽象示例包括:

用于在GUI(图形用户界面)中导航以访问地址的文件夹图标,而不是键入实际地址以导航到某个位置。GUI滑块用于控制不同级别的音量、文档滚动位置等。。

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

我相信提问者正在考虑使用哈希,这样在放置袜子之前,应该知道袜子的位置。

这就是为什么我建议将放在地板上的一只袜子抽象为哈希键本身(因此不需要复制袜子)。

如何定义哈希键?

如果有不止一双类似的袜子,下面的密钥定义也适用。也就是说,假设有两双黑色男士袜子PairA和PairB,每双袜子都被命名为PairA-L、PairA-R、PairB-L和PairB-R。因此,PairA-L可以与PairB-R配对,但PairA-L和PairB-L不能配对。

假设任何袜子都可以通过以下方式唯一标识,

属性[性别]+属性[颜色]+属性(材质)+属性[类型1]+属性[类别2]+属性[左_右]

这是我们的第一个哈希函数。让我们对这个h1(G_C_M_T1_T2_LR)使用一个简短的符号。h1(x)不是我们的位置键。

消除Left_or_Right属性的另一个哈希函数是h2(G_C_M_T1_T2)。第二个函数h2(x)是我们的位置键!(你身后地板上的空间)。

要定位插槽,请使用h2(G_C_M_T1_T2)。一旦找到了槽,就使用h1(x)来检查它们的哈希值。如果它们不匹配,你就有一对。否则,把袜子扔到同一个槽里。

注意:由于我们在找到一个插槽时删除了一个插槽,因此可以安全地假设最多只有一个插槽具有唯一的h2(x)或h1(x)值。

如果我们每只袜子正好有一对匹配的袜子,那么使用h2(x)来查找位置,如果没有袜子,则需要进行检查,因为可以安全地假设它们是一对。

为什么把袜子放在地板上很重要

让我们考虑一个场景,袜子堆在一起(最坏的情况)。这意味着我们别无选择,只能进行线性搜索来找到一对。

将它们铺在地板上可以提高可见度,从而提高发现匹配袜子(匹配哈希键)的机会。当第三步把袜子放在地板上时,我们的大脑已经下意识地记录了位置。-因此,如果这个位置在我们的内存中可用,我们可以直接找到匹配的配对。-如果没有记住位置,不要担心,然后我们可以一直返回到线性搜索。

为什么从地板上取下这对鞋很重要?

短期人类记忆在需要记忆的项目较少时效果最好。因此,增加了我们使用哈希来识别这对的概率。当使用线性搜索对时,它还将减少要搜索的项目的数量。

分析

情况1:最坏的情况是,Derpina无法记住或直接使用哈希技术在地板上发现袜子。Derp对地板上的物品进行线性搜索。这并不比遍历堆以找到对更糟。比较上限:O(n^2)。比较下限:(n/2)。(当Derpina每捡一只袜子都是上一只的时候)。案例2:德普记得他放在地板上的每一只袜子的位置,每只袜子正好有一双。比较上限:O(n/2)。比较下限:O(n/2)。

我说的是比较操作,从袜子堆里挑选袜子必然是n次操作。因此,实际的下限是n次迭代,n/2次比较。

加快进度

为了获得完美的分数,使Derp获得O(n/2)比较,我建议Derpina,

花更多时间穿袜子来熟悉它。是的,这意味着也要花更多时间穿着德普的袜子。玩记忆游戏,如在网格中找出对,可以提高短期记忆性能,这是非常有益的。

这是否等同于元素清晰度问题?

我建议的方法是用于解决元素区分问题的方法之一,将它们放在哈希表中并进行比较。

考虑到您的特殊情况,即只有一个精确的对,它已经变得非常等价于元素区别问题。因为我们甚至可以对袜子进行分类,并检查相邻袜子是否成对(EDP的另一种解决方案)。

然而,如果给定袜子可能存在不止一双,那么它就偏离了EDP。

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

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

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

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

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

我们必须进行比较,以检查两只袜子是否成对。选择基于O(n log 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类错误而未配对的剩余可配对袜子进行配对。哎呦,你完了——我有很多袜子,直到大部分都脏了才洗。另一个实际注意事项是:我将一双袜子的顶部翻转到另一双袜子上,利用它们的弹性财产,以便它们在被运送到抽屉和抽屉中时保持在一起。