昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在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的值!但人们可能会再次反对,因为您可能很难找到(或创建)每只袜子的集群。

此外,你也可以在网站上查找最佳算法,并提出自己的解决方案,从而节省时间:)

你试图解决错误的问题。

解决方案1:每次你把脏袜子放进洗衣篮时,把它们打个小结。这样你就不用在洗完衣服后做任何分类了。把它想象成在Mongo数据库中注册索引。未来需要做一些工作来节省CPU。

解决方案2:如果是冬天,你不必穿配套的袜子。我们是程序员。没有人需要知道,只要它有效。

解决方案3:分散工作。您希望异步执行如此复杂的CPU进程,而不阻塞UI。把那堆袜子塞进袋子里。只有在你需要的时候才找一双。这样,你的工作量就不那么明显了。

希望这有帮助!

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

几乎所有其他算法(包括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)边界。我的直觉是:考虑一个测试后添加边的图形,并认为如果图形不密集,则输出不是唯一确定的。