昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家,我在想我能做什么?排序(根据大小/颜色/…)当然是为了实现O(NlogN)解决方案。
哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。
因此,问题基本上是:
给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)
我将感谢回答以下方面的问题:
大量袜子的一般理论解。袜子的实际数量没有那么多,我不相信我的配偶和我有超过30双。(而且很容易区分我的袜子和她的袜子;这也可以用吗?)它是否等同于元素清晰度问题?
我提出的解决方案假设所有袜子在细节上都是相同的,除了颜色。如果袜子之间有更多的细节需要延迟,这些细节可以用来定义不同类型的袜子,而不是我的例子中的颜色。。
假设我们有一堆袜子,袜子可以有三种颜色:蓝色、红色或绿色。
然后,我们可以为每种颜色创建一个并行工作程序;它有自己的列表来填充相应的颜色。
At time i:
Blue read Pile[i] : If Blue then Blue.Count++ ; B=TRUE ; sync
Red read Pile[i+1] : If Red then Red.Count++ ; R=TRUE ; sync
Green read Pile [i+2] : If Green then Green.Count++ ; G=TRUE ; sync
同步过程:
Sync i:
i++
If R is TRUE:
i++
If G is TRUE:
i++
这需要初始化:
Init:
If Pile[0] != Blue:
If Pile[0] = Red : Red.Count++
Else if Pile[0] = Green : Green.Count++
If Pile[1] != Red:
If Pile[0] = Green : Green.Count++
哪里
Best Case: B, R, G, B, R, G, .., B, R, G
Worst Case: B, B, B, .., B
Time(Worst-Case) = C * n ~ O(n)
Time(Best-Case) = C * (n/k) ~ O(n/k)
n: number of sock pairs
k: number of colors
C: sync overhead
我在攻读计算机科学博士期间经常思考这个问题。我提出了多种解决方案,这取决于区分袜子的能力,从而尽可能快地找到正确的袜子。
假设看袜子和记住它们独特图案的成本可以忽略不计(ε)。那么最好的解决办法就是把所有的袜子都扔到桌子上。这包括以下步骤:
将所有袜子放在一张桌子上(1),并创建一个hashmap{pattern:position}(ε)当有剩余袜子时(n/2):随机挑选一只袜子(1)查找相应袜子的位置(ε)取回袜子(1)并存放
这确实是最快的可能性,并且以n+1=O(n)复杂度执行。但它假设你完全记得所有的模式。。。在实践中,情况并非如此,我个人的经验是,你有时在第一次尝试时找不到匹配的一对:
把所有袜子扔在桌子上(1)当有剩余袜子时(n/2):随机挑选一只袜子(1)当未配对时(1/P):找到具有相似图案的袜子拿袜子,比较两者(1)如果可以,存储配对
这现在取决于我们找到匹配对的能力。如果你的深色/灰色双鞋或白色运动袜经常有非常相似的图案,这一点尤其正确!让我们承认你有概率找到相应的袜子。在找到相应的袜子以形成一双袜子之前,平均需要1/P的尝试。总体复杂度为1+(n/2)*(1+1/P)=O(n)。
两者在袜子数量上都是线性的,并且是非常相似的解决方案。让我们稍微修改一下这个问题,承认你有多双类似的袜子,并且很容易在一次移动中存储多双袜子(1+ε)。对于K个不同的模式,您可以实现:
对于每只袜子(n):随机挑选一只袜子(1)将其放到其模式的集群中对于每个集群(K):取簇并储存袜子(1+ε)
总体复杂度变为n+K=O(n)。它仍然是线性的,但选择正确的算法现在可能很大程度上取决于P和K的值!但人们可能会再次反对,因为您可能很难找到(或创建)每只袜子的集群。
此外,你也可以在网站上查找最佳算法,并提出自己的解决方案,从而节省时间:)
当我对袜子进行排序时,我会进行近似基数排序,将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近,我能看到一对完全匹配的袜子,否则我会在那一刻取出这双袜子。
几乎所有其他算法(包括usr评分最高的答案)排序,然后删除配对。我发现,作为一个人,一次考虑的袜子数量最好尽量减少。
我通过以下方式做到这一点:
挑选一只与众不同的袜子(在袜子堆里最先映入我眼帘的东西)。从概念位置开始基数排序,根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近,距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面,因为它是相同的,请在那里形成一对,然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。
这利用了人类在O(1)时间内进行模糊匹配的能力,这在某种程度上相当于在计算设备上建立哈希图。
通过先穿上与众不同的袜子,你可以留出空间来“放大”那些不那么与众不同的特征。
在去除了浅色、条纹袜子和三双长袜之后,你可能最终会得到大致按磨损程度分类的白色袜子。
在某种程度上,袜子之间的差异很小,以至于其他人不会注意到差异,因此不需要进一步的匹配。
袜子,无论是真的还是类似的数据结构,都将成对提供。
最简单的答案是,在允许袜子对分开之前,应该初始化袜子对的单个数据结构,该结构包含指向左右袜子的指针,从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。
这通过使用抽象层来消除任何计算配对问题。
将同样的想法应用于袜子配对的实际问题,显而易见的答案是:不要让你的袜子不配对。袜子是一双提供的,一双放在抽屉里(也许是把它们捆在一起),一双穿。但可能脱漆的地方是在洗衣机里,所以所需要的只是一个物理机制,让袜子保持在一起并有效地清洗。
有两种物理可能性:
对于一个“pair”对象,它保持指向每只袜子的指针,我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。
但是,为了让每一只袜子都能互相参照,有一个很好的解决方案:一个popper(如果你是美国人,可以使用“按扣”),比如:
http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html
然后,你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起,再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。
这是基于比较的模型中的Omega(n log n)下限。(唯一有效的操作是比较两只袜子。)
假设你知道你的2n只袜子是这样排列的:
p1 p2 p3。。。pn pf(1)pf(2)。。。功率因数(n)
其中f是集合{1,2,…,n}的未知排列。知道这一点不会使问题变得更难。有n个!可能的输出(上半部分和下半部分之间的匹配),这意味着您需要log(n!)=Omega(n log n)比较。这可通过分类获得。
由于您对元素区别性问题的连接感兴趣:证明元素区别性的Omega(n log n)界限比较困难,因为输出是二进制的yes/no。这里,输出必须是匹配的,并且可能输出的数量足以获得一个合适的界限。然而,有一个变量与元素的区别有关。假设你有2n只袜子,想知道它们是否可以唯一配对。您可以通过将(a1,a2,…,an)发送到(a1,a1,a2、a2,…、an,an)来获得ED的缩减。(附带地,通过拓扑结构,ED的硬度证明非常有趣。)
我认为,如果只允许等式测试,那么原始问题应该有一个Omega(n2)边界。我的直觉是:考虑一个测试后添加边的图形,并认为如果图形不密集,则输出不是唯一确定的。