昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在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);
}
至少这是我在现实生活中使用的,我发现它非常有效。缺点是它需要一个平坦的表面,但通常很丰富。
这是基于比较的模型中的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)边界。我的直觉是:考虑一个测试后添加边的图形,并认为如果图形不密集,则输出不是唯一确定的。
我提出了另一个解决方案,它不会承诺更少的操作,也不会减少时间消耗,但应该尝试看看它是否能成为一个足够好的启发式方法,在大量袜子配对中提供更少的时间消耗。
前提条件:不能保证有相同的袜子。如果它们的颜色相同,并不意味着它们的大小或图案相同。袜子随机洗牌。袜子的数量可能是奇数(有些不见了,我们不知道有多少)。准备记住一个变量“index”并将其设置为0。
结果将有一个或两个桩:1。“匹配”和2。“缺少”
启发式:
找到最与众不同的袜子。找到匹配项。如果没有匹配项,请将其放在“缺失”堆上。从1开始重复。直到没有最与众不同的袜子。如果袜子少于6只,请转到11只。盲目地将所有袜子与邻居配对(不要打包)找到所有匹配的对,将其打包并将打包的对移动到“匹配”的堆中;如果没有新的匹配项-将“索引”增加1如果“index”大于2(这可能取决于袜子的值因为袜子数量越多盲目配对)进入11打乱其余的转到1忘记“索引”挑选一只袜子查找其配对如果没有袜子,就把它移到“失踪”的那一堆如果找到匹配项,将其配对,将其打包并移动到“匹配”堆中如果还有不止一只袜子,那就去12只如果只剩下一个,请转到14满意的微笑:)
此外,还可以添加检查袜子是否损坏,就像移除袜子一样。它可以插入2到3之间,13到14之间。
我期待听到任何经验或更正。
我提出的解决方案假设所有袜子在细节上都是相同的,除了颜色。如果袜子之间有更多的细节需要延迟,这些细节可以用来定义不同类型的袜子,而不是我的例子中的颜色。。
假设我们有一堆袜子,袜子可以有三种颜色:蓝色、红色或绿色。
然后,我们可以为每种颜色创建一个并行工作程序;它有自己的列表来填充相应的颜色。
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