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

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

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

因此,问题基本上是:

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

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

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


当前回答

我提出了另一个解决方案,它不会承诺更少的操作,也不会减少时间消耗,但应该尝试看看它是否能成为一个足够好的启发式方法,在大量袜子配对中提供更少的时间消耗。

前提条件:不能保证有相同的袜子。如果它们的颜色相同,并不意味着它们的大小或图案相同。袜子随机洗牌。袜子的数量可能是奇数(有些不见了,我们不知道有多少)。准备记住一个变量“index”并将其设置为0。

结果将有一个或两个桩:1。“匹配”和2。“缺少”

启发式:

找到最与众不同的袜子。找到匹配项。如果没有匹配项,请将其放在“缺失”堆上。从1开始重复。直到没有最与众不同的袜子。如果袜子少于6只,请转到11只。盲目地将所有袜子与邻居配对(不要打包)找到所有匹配的对,将其打包并将打包的对移动到“匹配”的堆中;如果没有新的匹配项-将“索引”增加1如果“index”大于2(这可能取决于袜子的值因为袜子数量越多盲目配对)进入11打乱其余的转到1忘记“索引”挑选一只袜子查找其配对如果没有袜子,就把它移到“失踪”的那一堆如果找到匹配项,将其配对,将其打包并移动到“匹配”堆中如果还有不止一只袜子,那就去12只如果只剩下一个,请转到14满意的微笑:)

此外,还可以添加检查袜子是否损坏,就像移除袜子一样。它可以插入2到3之间,13到14之间。

我期待听到任何经验或更正。

其他回答

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

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

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

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

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

算法答案:

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

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

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

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

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

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

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

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

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

真实世界方法:

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

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

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

机器

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

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

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

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

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

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

算法

我的建议是:

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从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只袜子是否属于同一对。这可能在每种情况下都不可行。