从你的问题来看，你显然没有太多洗衣方面的实际经验：）。你需要一种算法，能很好地处理少量不可配对的袜子。

到目前为止，答案还没有充分利用我们的人类模式识别能力。集合游戏提供了如何做好这一点的线索：将所有袜子放在一个二维空间中，这样你就可以很好地识别它们，并用手轻松地够到它们。这将您的面积限制在120*80厘米左右。从那里选择您识别的配对并将其删除。将多余的袜子放在空闲空间，然后重复。如果你为穿着容易辨认的袜子的人洗衣服（脑海中浮现的是小孩子），你可以先选择袜子来进行基数排序。该算法仅在单袜子数量较少时有效

对于p双袜子（n=2p只袜子），我实际上是这样做的：

从袜子堆里随便拿一只袜子。对于第一只袜子，或者如果之前选择的所有袜子都已配对，只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子，请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时，可以将袜子分为普通类别或类型（白色/黑色、脚踝/圆领、运动型/连衣裙），并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配，把两只袜子放在一起，然后把它们从阵列中去掉。如果没有，请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。

这种方案的最坏情况是，每双袜子都不同，必须完全匹配，而且你挑选的第一双n/2袜子都不同。这是你的O（n2）场景，极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2，并且每种类型的袜子都足够相似（通常在穿着相关的术语中），使得该类型的任何袜子都可以与任何其他袜子配对，那么正如我上面所推断的，你必须与之进行比较的袜子的最大数量是t，之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生，并将最坏情况的复杂性降低到O（n*t），其中通常t<<n。

如果“移动”操作相当昂贵，而“比较”操作很便宜，并且无论如何都需要将整个集合移动到一个缓冲区中，在那里搜索速度比原始存储快得多。。。只需将排序整合到强制移动中即可。

我发现，将分拣过程整合到晾衣架中，这一过程变得轻而易举。无论如何，我需要拿起每一只袜子，然后把它挂起来（移动），把它挂在绳子上的某个特定位置几乎不需要任何费用。现在，为了不强制搜索整个缓冲区（字符串），我选择按颜色/阴影放置袜子。左边更黑，右边更亮，前面更鲜艳。现在，在我挂上每一只袜子之前，我先看看它的“右边附近”是否已经有一只匹配的袜子——这限制了“扫描”其他2-3只袜子——如果有，我就把另一只挂在旁边。然后，我把它们成对地卷起来，然后在干的时候把它们从绳子上取下来。

现在，这似乎与顶级答案所建议的“按颜色形成桩”没有什么不同，但首先，通过不选择离散桩而是选择范围，我没有问题将“紫色”分类为“红色”还是“蓝色”桩；它只是介于两者之间。然后通过集成两个操作（挂起晾干和分拣），挂起时的分拣开销大约是单独分拣的10%。

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

这是基于比较的模型中的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）边界。我的直觉是：考虑一个测试后添加边的图形，并认为如果图形不密集，则输出不是唯一确定的。

整理n双袜子的问题是O（n）。在你把它们扔进洗衣篮之前，你先把左边的衣服穿到右边的衣服上。取出时，你剪下线，把每一对线放进抽屉里——对n对线进行2次操作，所以O（n）。

现在，下一个问题很简单，你是自己洗衣服，还是妻子洗衣服。这可能是一个完全不同领域的问题。：）