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

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

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

因此,问题基本上是:

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

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

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


当前回答

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

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

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

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

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

其他回答

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

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

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

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

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

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

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

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

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

我已经采取了简单的步骤,将我的努力减少到一个需要O(1)时间的过程中。

通过将我的输入减少到两种袜子中的一种(休闲用的白色袜子,工作用的黑色袜子),我只需要确定手中有哪种袜子。(从技术上讲,由于它们从未一起清洗过,我已将过程缩短到O(0)时间。)

为了找到合适的袜子,需要提前付出一些努力,并购买足够数量的袜子,以消除对现有袜子的需求。因为我在需要黑色袜子之前就已经做了这件事,所以我的努力很小,但里程可能会有所不同。

这种前期工作在非常流行和有效的代码中已经多次出现。示例包括#DEFINE'将圆周率定义为几个小数(其他示例也存在,但这是我现在想到的)。

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

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

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

算法答案:

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

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

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

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

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

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

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

作为实际解决方案:

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

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