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

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

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

因此,问题基本上是:

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

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

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


当前回答

由于人脑的结构与现代CPU完全不同,所以这个问题毫无实际意义。

人类可以利用“找到匹配的对”这一事实来战胜CPU算法,这对于一个不太大的集合来说是一个操作。

我的算法:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

至少这是我在现实生活中使用的,我发现它非常有效。缺点是它需要一个平坦的表面,但通常很丰富。

其他回答

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

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

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

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

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

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

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

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

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

对于p双袜子(n=2p只袜子),我实际上是这样做的:

从袜子堆里随便拿一只袜子。对于第一只袜子,或者如果之前选择的所有袜子都已配对,只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子,请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时,可以将袜子分为普通类别或类型(白色/黑色、脚踝/圆领、运动型/连衣裙),并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配,把两只袜子放在一起,然后把它们从阵列中去掉。如果没有,请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。

这种方案的最坏情况是,每双袜子都不同,必须完全匹配,而且你挑选的第一双n/2袜子都不同。这是你的O(n2)场景,极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2,并且每种类型的袜子都足够相似(通常在穿着相关的术语中),使得该类型的任何袜子都可以与任何其他袜子配对,那么正如我上面所推断的,你必须与之进行比较的袜子的最大数量是t,之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生,并将最坏情况的复杂性降低到O(n*t),其中通常t<<n。

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

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

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

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

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

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

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

我刚刚完成袜子配对,我发现最好的方法是:

选择一只袜子并将其收起来(为这双袜子创建一个“水桶”)如果下一个是上一个的一对,则将其放到现有的存储桶中,否则创建一个新的存储桶。

在最坏的情况下,这意味着您将有n/2个不同的存储桶,并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然,如果你只有几对,这个算法会很好地工作;我用了12双鞋。

它不是那么科学,但它工作得很好:)