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

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

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

因此,问题基本上是:

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

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

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


当前回答

为了说明从一堆袜子中配对有多有效,我们必须首先定义机器,因为配对不是通过图灵或随机存取机器完成的,而随机存取机器通常用作算法分析的基础。

机器

机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的(希望是;-)。

我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制,由手臂或眼睛执行的操作具有非恒定的时间复杂性。这是因为我们不能用手臂移动一大堆无穷无尽的袜子,也不能用眼睛看到一大堆袜子上的袜子。

然而,机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。

因此,根据之前的分析,应按降序使用以下操作:

逻辑和算术运算环境读数环境改造

我们还可以利用这样一个事实,即人们只有非常有限的袜子。因此,环境改造可能涉及到所有袜子。

算法

我的建议是:

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从2开始重复,直到无法配对。从1开始重复,直到地板上没有袜子。

操作4是必要的,因为当将袜子铺在地板上时,一些袜子可能会隐藏其他袜子。算法分析如下:

分析

该算法以高概率终止。这是由于在第二步中找不到袜子。

对于以下对n双袜子配对的运行时分析,我们假设在步骤1之后,至少有一半的2n双袜子没有隐藏。所以在平均情况下,我们可以找到n/2对。这意味着步骤4的循环执行了O(logn)次。步骤2执行O(n^2)次。因此,我们可以得出结论:

该算法涉及O(lnn+n)环境修改(步骤1 O(lnn)加上从地板上挑选每双袜子)该算法涉及步骤2中的O(n^2)个环境读数该算法包括O(n^2)个逻辑和算术运算,用于在步骤2中比较袜子和另一袜子

因此,我们的总运行时复杂度为O(r*n^2+w*(lnn+n)),其中r和w分别是合理数量袜子的环境读取和环境写入操作的因素。省略了逻辑运算和算术运算的成本,因为我们假设需要恒定数量的逻辑运算和算数运算来决定2只袜子是否属于同一对。这可能在每种情况下都不可行。

其他回答

我所做的就是拿起第一只袜子,把它放下(比如,放在洗衣碗的边缘)。然后我拿起另一只袜子,检查它是否与第一只袜子相同。如果是,我会把它们都去掉。如果不是,我把它放在第一只袜子旁边。然后我拿起第三只袜子,将其与前两只袜子进行比较(如果它们还在的话)。等

这种方法可以很容易地在阵列中实现,假设“移除”袜子是一个选项。实际上,你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序(见下文),那么您只需移动它们,就可以得到一个数组,该数组中所有袜子都成对排列。

假设袜子的唯一操作是比较相等,这个算法基本上仍然是n2算法,尽管我不知道平均情况(从未学会计算)。

当然,分类可以提高效率,尤其是在现实生活中,你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中,树也可以做到这一点,但这是额外的空间。当然,我们又回到了NlogN(或者更多,如果有几只袜子按排序标准是相同的,但不是来自同一双)。

除此之外,我想不出什么,但这种方法在现实生活中似乎非常有效

每当你拿起袜子时,把它放在一个地方。然后你拿起的下一只袜子,如果它与第一只袜子不匹配,就把它放在第一只袜子旁边。如果是,那就有一对。这样,有多少种组合其实并不重要,而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配,要么它没有匹配,这意味着你将它添加到数组中的一个位置。

这也意味着你几乎肯定不会把所有袜子都放在阵列中,因为袜子会在搭配时被取下。

做一些预处理怎么样?我会在每只袜子上缝上一个标记或身份证号码,这样每双袜子都有相同的标记/身份证号码。这个过程可能在你每次买一双新袜子时都会完成。然后,您可以进行基数排序以获得O(n)总成本。为每个标记/身份证号码找一个位置,只需逐一挑选所有袜子并将它们放在正确的位置。

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

在你身后的地板上做两个假想的部分,一个给你,另一个给配偶。从袜子堆里取一只。现在,按照以下规则将袜子一只一只地放在地板上。确定袜子是你的还是她的,并查看地板上的相关部分。如果你能在地板上找到这双鞋,就把它捡起来,把它们系起来,或者把它们夹起来,或者在找到一双鞋后做任何你想做的事情,然后把它放在篮子里(把它从地板上取下来)。将其放在相关章节中。重复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步)去沃尔玛买10-n包的白色和m包黑色。日常无需其他颜色生活

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

算法答案:

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

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

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

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

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

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

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