昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在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之间。

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

其他回答

当我对袜子进行排序时,我会进行近似基数排序,将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近,我能看到一对完全匹配的袜子,否则我会在那一刻取出这双袜子。

几乎所有其他算法(包括usr评分最高的答案)排序,然后删除配对。我发现,作为一个人,一次考虑的袜子数量最好尽量减少。

我通过以下方式做到这一点:

挑选一只与众不同的袜子(在袜子堆里最先映入我眼帘的东西)。从概念位置开始基数排序,根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近,距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面,因为它是相同的,请在那里形成一对,然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。

这利用了人类在O(1)时间内进行模糊匹配的能力,这在某种程度上相当于在计算设备上建立哈希图。

通过先穿上与众不同的袜子,你可以留出空间来“放大”那些不那么与众不同的特征。

在去除了浅色、条纹袜子和三双长袜之后,你可能最终会得到大致按磨损程度分类的白色袜子。

在某种程度上,袜子之间的差异很小,以至于其他人不会注意到差异,因此不需要进一步的匹配。

由于人脑的结构与现代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);
}

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

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

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

考虑大小为“N”的哈希表。

如果我们假设正态分布,那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN(即,所有存储桶都已满)

我将此作为另一个谜题的一部分,但我很乐意被证明是错误的。这是我的博客文章

让“N”对应于袜子独特颜色/图案数量的近似上限。

一旦发生碰撞(也就是火柴),只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于,由于人类思维的方式,你可以进行NlogN并行比较(冲突解决)

Defant&Kravitz(1)给出了一种算法,通过将袜子依次放在脚上和脚下来对袜子进行排序。

他们的算法适用于任意数量的英尺。

本文给出了(定理1.1)可使用单脚排序的袜子订单的特征。从他们的定理1.3可以看出,每一个4种颜色的袜子订单最多可以用两只脚进行排序,而有5种颜色的袜订单不可能用两只脚排序。

Colin Defant和Noah Kravitz,袜子足部分类(2022)