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

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

作为实际解决方案：

快速制作一堆易于区分的袜子。（用颜色表示）快速整理每一堆，并使用袜子的长度进行比较。作为一个人，你可以很快地决定用哪只袜子进行分区，以避免最坏的情况。（你可以看到多只袜子平行排列，这对你有利！）当垃圾堆达到一个阈值时，停止分类，在该阈值下，您可以立即找到不合适的袜子和短袜

如果你有1000只袜子，有8种颜色，平均分布，你可以在c*n时间内每125只袜子做4堆。以5只袜子为阈值，你可以在6次跑步中对每一堆袜子进行分类。（数2秒把袜子扔到正确的堆上，只需要不到4小时。）

如果你只有60只袜子、3种颜色和2种袜子（你/你妻子的），你可以在1次跑步中对每一堆10只袜子进行分类（同样阈值=5）。（数2秒，需要2分钟）。

最初的桶排序将加快您的进程，因为它在c*n时间内将n个袜子分成k个桶，因此您只需执行c*n*log（k）工作。（不考虑阈值）。所以，你所做的所有关于n*c*（1+log（k））的工作，其中c是把袜子扔在一堆上的时间。

与任何c*x*n+O（1）方法相比，只要log（k）<x-1，该方法将是有利的。

---

在计算机科学中，这可能很有用：我们有一个n个事物的集合，它们的顺序（长度）和等价关系（额外的信息，例如袜子的颜色）。等价关系允许我们对原始集合进行分区，并且在每个等价类中我们的顺序仍然保持不变。一个事物到它的等价类的映射可以在O（1）中完成，因此只需要O（n）就可以将每个项分配给一个类。现在我们已经使用了额外的信息，可以以任何方式对每个类进行排序。其优点是数据集已经明显更小。

该方法也可以嵌套，如果我们有多个等价关系->使颜色堆积，而不是在纹理上的每个堆积分区内，而不是按长度排序。任何等价关系如果创建一个分区，其中包含2个以上的元素，且大小大致相等，那么与排序相比，排序的速度都会有所提高（前提是我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上快速进行。

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

机器

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

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

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

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

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

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

算法

我的建议是：

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从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只袜子是否属于同一对。这可能在每种情况下都不可行。

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

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

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

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

如果你可以将一双袜子抽象为密钥本身，将另一双袜子作为值，那么我们可以使用哈希来发挥作用。

在你身后的地板上做两个假想的部分，一个给你，另一个给配偶。从袜子堆里取一只。现在，按照以下规则将袜子一只一只地放在地板上。确定袜子是你的还是她的，并查看地板上的相关部分。如果你能在地板上找到这双鞋，就把它捡起来，把它们系起来，或者把它们夹起来，或者在找到一双鞋后做任何你想做的事情，然后把它放在篮子里（把它从地板上取下来）。将其放在相关章节中。重复3次，直到所有袜子都从袜子堆上取下。

说明：

哈希和抽象

抽象是一个非常强大的概念，已用于改善用户体验（UX）。现实生活中与计算机交互的抽象示例包括：

用于在GUI（图形用户界面）中导航以访问地址的文件夹图标，而不是键入实际地址以导航到某个位置。GUI滑块用于控制不同级别的音量、文档滚动位置等。。

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

我相信提问者正在考虑使用哈希，这样在放置袜子之前，应该知道袜子的位置。

这就是为什么我建议将放在地板上的一只袜子抽象为哈希键本身（因此不需要复制袜子）。

如何定义哈希键？

如果有不止一双类似的袜子，下面的密钥定义也适用。也就是说，假设有两双黑色男士袜子PairA和PairB，每双袜子都被命名为PairA-L、PairA-R、PairB-L和PairB-R。因此，PairA-L可以与PairB-R配对，但PairA-L和PairB-L不能配对。

假设任何袜子都可以通过以下方式唯一标识，

属性[性别]+属性[颜色]+属性（材质）+属性[类型1]+属性[类别2]+属性[左_右]

这是我们的第一个哈希函数。让我们对这个h1（G_C_M_T1_T2_LR）使用一个简短的符号。h1（x）不是我们的位置键。

消除Left_or_Right属性的另一个哈希函数是h2（G_C_M_T1_T2）。第二个函数h2（x）是我们的位置键！（你身后地板上的空间）。

要定位插槽，请使用h2（G_C_M_T1_T2）。一旦找到了槽，就使用h1（x）来检查它们的哈希值。如果它们不匹配，你就有一对。否则，把袜子扔到同一个槽里。

注意：由于我们在找到一个插槽时删除了一个插槽，因此可以安全地假设最多只有一个插槽具有唯一的h2（x）或h1（x）值。

如果我们每只袜子正好有一对匹配的袜子，那么使用h2（x）来查找位置，如果没有袜子，则需要进行检查，因为可以安全地假设它们是一对。

为什么把袜子放在地板上很重要

让我们考虑一个场景，袜子堆在一起（最坏的情况）。这意味着我们别无选择，只能进行线性搜索来找到一对。

将它们铺在地板上可以提高可见度，从而提高发现匹配袜子（匹配哈希键）的机会。当第三步把袜子放在地板上时，我们的大脑已经下意识地记录了位置。-因此，如果这个位置在我们的内存中可用，我们可以直接找到匹配的配对。-如果没有记住位置，不要担心，然后我们可以一直返回到线性搜索。

为什么从地板上取下这对鞋很重要？

短期人类记忆在需要记忆的项目较少时效果最好。因此，增加了我们使用哈希来识别这对的概率。当使用线性搜索对时，它还将减少要搜索的项目的数量。

分析

情况1：最坏的情况是，Derpina无法记住或直接使用哈希技术在地板上发现袜子。Derp对地板上的物品进行线性搜索。这并不比遍历堆以找到对更糟。比较上限：O（n^2）。比较下限：（n/2）。（当Derpina每捡一只袜子都是上一只的时候）。案例2：德普记得他放在地板上的每一只袜子的位置，每只袜子正好有一双。比较上限：O（n/2）。比较下限：O（n/2）。

我说的是比较操作，从袜子堆里挑选袜子必然是n次操作。因此，实际的下限是n次迭代，n/2次比较。

加快进度

为了获得完美的分数，使Derp获得O（n/2）比较，我建议Derpina，

花更多时间穿袜子来熟悉它。是的，这意味着也要花更多时间穿着德普的袜子。玩记忆游戏，如在网格中找出对，可以提高短期记忆性能，这是非常有益的。

这是否等同于元素清晰度问题？

我建议的方法是用于解决元素区分问题的方法之一，将它们放在哈希表中并进行比较。

考虑到您的特殊情况，即只有一个精确的对，它已经变得非常等价于元素区别问题。因为我们甚至可以对袜子进行分类，并检查相邻袜子是否成对（EDP的另一种解决方案）。

然而，如果给定袜子可能存在不止一双，那么它就偏离了EDP。