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

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

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

因此,问题基本上是:

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

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

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


当前回答

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

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

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

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

其他回答

每当你拿起袜子时,把它放在一个地方。然后你拿起的下一只袜子,如果它与第一只袜子不匹配,就把它放在第一只袜子旁边。如果是,那就有一对。这样,有多少种组合其实并不重要,而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配,要么它没有匹配,这意味着你将它添加到数组中的一个位置。

这也意味着你几乎肯定不会把所有袜子都放在阵列中,因为袜子会在搭配时被取下。

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

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

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

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

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

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

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

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

这是问错了问题。正确的问题是,我为什么要花时间整理袜子?如果你选择X个货币单位来计算你的空闲时间,那么每年的花费是多少?

通常情况下,这不仅仅是任何空闲时间,这是早晨的空闲时间,你可以躺在床上,或者喝咖啡,或者早点离开,不被交通堵塞。

退一步想办法解决问题通常是好的。

还有一个办法!

找一只你喜欢的袜子。考虑所有相关特征:不同照明条件下的颜色、整体质量和耐久性、不同气候条件下的舒适性以及气味吸收。同样重要的是,它们在储存过程中不应失去弹性,所以天然织物是好的,它们应该可以用塑料包装。

如果左脚和右脚的袜子没有区别,那就更好了,但这并不重要。如果袜子是左右对称的,找到一双袜子是O(1)运算,而对袜子进行排序是近似的O(M)运算,其中M是你家里扔袜子的地方的数量,理想情况下是一个小常数。

如果你选择了一双左右袜子不同的奇装异服,对左脚和右脚的桶进行全桶排序,取O(N+M),其中N是袜子的数量,M与上述相同。其他人可以给出找到第一双袜子的平均迭代次数的公式,但通过盲搜索找到一双袜子的最坏情况是N/2+1,对于合理的N来说,这在天文学上是不太可能的。当用Mk1 Eyeball扫描一堆未分类的袜子时,使用先进的图像识别算法和启发式方法可以加快速度。

因此,实现O(1)袜子配对效率的算法(假设对称袜子)为:

你需要估计你的余生需要多少双袜子,或者直到你退休并搬到更温暖的气候,不再需要穿袜子。如果你还年轻,你还可以估计我们需要多长时间才能在家里拥有袜子分拣机器人,而整个问题变得无关紧要。您需要了解如何批量订购您选择的袜子,以及它的价格,以及它们的送货方式。订购袜子!扔掉你的旧袜子。

另一个步骤3将包括比较几年来一次购买几双同样数量的可能更便宜的袜子的成本,并加上整理袜子的成本。但我要保证:批量购买更便宜!此外,库存袜子的价值会随着股价的上涨而增加,这比你在很多投资中得到的要多。此外,还有存储成本,但袜子确实不会占用壁橱顶部货架上的空间。

问题已解决。所以,只要买一双新袜子,扔掉/捐赠你的旧袜子,在知道你的余生每天都在节省金钱和时间之后,就可以幸福地生活下去。

List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

我提出的解决方案假设所有袜子在细节上都是相同的,除了颜色。如果袜子之间有更多的细节需要延迟,这些细节可以用来定义不同类型的袜子,而不是我的例子中的颜色。。

假设我们有一堆袜子,袜子可以有三种颜色:蓝色、红色或绿色。

然后,我们可以为每种颜色创建一个并行工作程序;它有自己的列表来填充相应的颜色。

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