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

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

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

因此,问题基本上是:

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

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

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


当前回答

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

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

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

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

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

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

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

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

其他回答

创建一个哈希表,该表将用于不匹配的袜子,使用模式作为哈希。一只一只地重复袜子。如果袜子在哈希表中有图案匹配,请将袜子从表中取出并配对。如果袜子没有火柴,就把它放到桌子上。

为了说明从一堆袜子中配对有多有效,我们必须首先定义机器,因为配对不是通过图灵或随机存取机器完成的,而随机存取机器通常用作算法分析的基础。

机器

机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的(希望是;-)。

我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制,由手臂或眼睛执行的操作具有非恒定的时间复杂性。这是因为我们不能用手臂移动一大堆无穷无尽的袜子,也不能用眼睛看到一大堆袜子上的袜子。

然而,机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。

因此,根据之前的分析,应按降序使用以下操作:

逻辑和算术运算环境读数环境改造

我们还可以利用这样一个事实,即人们只有非常有限的袜子。因此,环境改造可能涉及到所有袜子。

算法

我的建议是:

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从2开始重复,直到无法配对。从1开始重复,直到地板上没有袜子。

操作4是必要的,因为当将袜子铺在地板上时,一些袜子可能会隐藏其他袜子。算法分析如下:

分析

该算法以高概率终止。这是由于在第二步中找不到袜子。

对于以下对n双袜子配对的运行时分析,我们假设在步骤1之后,至少有一半的2n双袜子没有隐藏。所以在平均情况下,我们可以找到n/2对。这意味着步骤4的循环执行了O(logn)次。步骤2执行O(n^2)次。因此,我们可以得出结论:

该算法涉及O(lnn+n)环境修改(步骤1 O(lnn)加上从地板上挑选每双袜子)该算法涉及步骤2中的O(n^2)个环境读数该算法包括O(n^2)个逻辑和算术运算,用于在步骤2中比较袜子和另一袜子

因此,我们的总运行时复杂度为O(r*n^2+w*(lnn+n)),其中r和w分别是合理数量袜子的环境读取和环境写入操作的因素。省略了逻辑运算和算术运算的成本,因为我们假设需要恒定数量的逻辑运算和算数运算来决定2只袜子是否属于同一对。这可能在每种情况下都不可行。

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);
  }
}

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

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

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

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

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

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