我想出了另一个解决方案，它不会承诺更少的操作，也不是更少的时间消耗，但应该尝试一下，看看它是否可以是一个足够好的启发式方法，在大量的袜子配对中提供更少的时间消耗。

前提条件：不能保证有相同的袜子。如果它们是相同的颜色，并不意味着它们有相同的尺寸或图案。袜子是随机洗牌的。袜子可以有奇数个（有些缺失，我们不知道有多少）。准备记住一个变量“index”并将其设置为0。

的结果将有一个或两个堆：1.“匹配”和2.“缺失”

启发式：

1. 找到最有特色的袜子。
2. 找到它的匹配。
3. 如果没有匹配，把它放在“丢失”的堆上。
4. 重复从1.直到没有更多的最独特的袜子。
5. 如果少于6只袜子，则转到11只。
6. 盲目地将所有袜子与邻居配对（不要打包）
7. 找到所有匹配的对，打包并将打包的对移动到“匹配”堆；如果没有新的匹配项-将“索引”增加1
8. 如果“index”大于2（这可能是取决于袜子的值数量，因为有更多的袜子有更少的机会将它们盲目配对）转到11
9. 把剩下的洗牌
10. 转到1
11. 忘记“索引”
12. 挑只袜子
13. 找到它的配对
14. 如果袜子没有一双，把它移到“丢失”的那堆
15. 如果匹配找到配对，打包配对并将其移动到“匹配”堆
16. 如果还有更多，那么一只袜子去12
17. 如果只剩下一个，去14
18. 满意的微笑：）

此外，还可以添加检查损坏的袜子，就像移除袜子一样。它可以插入2到3之间，13到14之间。

我期待着听到任何经验或更正。

做一些预处理怎么样？我会在每只袜子上缝一个标记或身份证号，以每双袜子都有相同的标记/身份证号的方式。这个过程可能在你每次购买一双新袜子时进行。然后，你可以做一个基数排序来获得O（n）的总成本。为每个标记/身份证号找到一个地方，然后逐一挑选所有袜子并将它们放在正确的地方。

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

这台机器

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

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

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

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

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

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

该算法

以下是我的建议：

1. 把袜子堆在地板上。
2. 通过看地板上的袜子找到一双。
3. 从2开始重复，直到没有配对。
4. 从1开始重复，直到地板上没有袜子。

操作4是必要的，因为当袜子在地板上传播时，一些袜子可能会隐藏其他袜子。以下是算法的分析：

的分析

该算法很可能会终止，这是因为在步骤2中找不到一双袜子。

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

• 该算法涉及O(ln n + n)环境修改（步骤1O(ln n)加上从地板上挑选每双袜子）
• 该算法涉及第2步的O(n^2)环境读取
• 该算法涉及O(n^2)逻辑和算术运算，用于在步骤2中将袜子与另一只袜子进行比较

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

这是一个错误的问题。正确的问题是，为什么我要花时间整理袜子？当你用你选择的X个货币单位来评估你的空闲时间时，每年花费多少钱？

通常情况下，这不仅仅是任何空闲时间，这是早上空闲时间，你可以在床上度过，或者喝咖啡，或者早点离开，不要被堵车。

退后一步，思考解决问题的方法通常是好的。

还有一个办法！

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

如果左脚和右脚的袜子没有区别会更好，但这不是关键。如果袜子是左右对称的，找到一双是O（1）操作，排序袜子是近似O（M）操作，其中M是你家里乱扔袜子的地方的数量，理想情况下是一些小的常数。

如果你选择了一双左右袜子不同的花哨的袜子，对左右脚桶进行完整的桶排序需要O（N+M），其中N是袜子的数量，M与上面相同。其他人可以给出找到第一对的平均迭代公式，但通过盲目搜索找到一对的最坏情况是N/2+1，这对于合理的N来说变得不太可能。

因此，实现O（1）袜子配对效率的算法（假设对称袜子）是：

1. 你需要估计你余生需要多少双袜子，或者直到你退休，搬到更温暖的气候，再也不用穿袜子。如果你还年轻，你还可以估计需要多长时间才能在我们的家中拥有袜子分类机器人，整个问题就变得无关紧要了。

2. 你需要找出如何批量订购你选择的袜子，它的成本是多少，他们是否交货。

3. 订购袜子！

4. 扔掉你的旧袜子。

第三步是比较购买同样数量的袜子的成本，一次买几双可能更便宜的袜子，然后加上分拣袜子的成本，但相信我的话：批量购买更便宜！此外，存储中的袜子以股价通胀的速度增值，这比你在许多投资中获得的要多。此外，还有存储成本，但袜子在壁橱顶层的空间并不大。

问题解决了。所以，买双新袜子，扔掉旧袜子，在知道你余生每天都在节省金钱和时间后，快乐地生活。

现实世界方法：

尽快地从未分类的袜子堆中取出袜子，一次一个地放在你前面的成堆的地方。成堆的袜子应该合理地排列，所有的袜子都指向同一个方向；成堆的数量受到你容易到达的距离的限制。选择放袜子的一堆应该-尽可能快-通过将袜子放在一堆看起来像袜子的堆上；偶尔的I型（将袜子放在不属于它的堆上）或II型（当存在一堆类似袜子时将袜子放在自己的堆上）错误可以容忍-最重要的考虑因素是速度。

一旦所有的袜子都成堆了，迅速穿过多袜子堆，创建成对并将其移除（这些是前往抽屉的）。如果有不匹配的袜子在堆中，将它们重新堆积到最佳状态（在尽可能快的约束范围内）。当所有的多袜子堆都处理完毕后，将剩余的由于类型II错误而未配对的可配对袜子配对起来。呼，你完成了--我有很多袜子，直到很大一部分脏了才洗。另一个实用的注意事项：我将一双袜子的顶部翻转到另一双上面，利用它们的弹性特性，所以它们在被运到抽屉和抽屉里时保持在一起。

我已经采取了一些简单的步骤，将我的努力减少到一个花费O（1）时间的过程中。

通过减少我对两种袜子中的一种的投入（休闲用的白袜子，工作用的黑袜子），我只需要确定我手里有哪两只袜子。（从技术上讲，因为它们从来没有一起洗过，我把这个过程减少到O（0）时间。）

为了找到合适的袜子，需要一些前期的努力，并购买足够的数量，以消除对现有袜子的需求。正如我在需要黑色袜子之前所做的那样，我的努力很小，但里程可能会有所不同。

这样的前期工作在非常流行和有效的代码中已经多次出现。例子包括#DEFINE'ing pi到几个小数（还有其他例子，但这是现在想到的）。

创建一个哈希表，将用于不匹配的袜子，使用模式作为哈希。逐个迭代袜子。如果袜子在哈希表中有匹配的模式，则将袜子从表中取出并制作一对。如果袜子没有匹配，则将其放入表中。

在我攻读计算机科学博士学位期间，我经常思考这个问题。我想出了多种解决方案，这取决于区分袜子的能力，从而尽可能快地找到正确的袜子。

假设查看袜子的成本和记住它们独特的模式是微不足道的（ε）。那么最好的解决方案就是简单地将所有袜子扔到一张桌子上。这包括以下步骤：

1. 将所有袜子扔到一张桌子上（1）并创建一个hashmap{模式：位置}（ε）
2. 剩下的袜子（n/2）：
   1. 随便拿一只袜子（1）
   2. 查找相应袜子的位置（ε）
   3. 取回袜子（1）并储存一对

这确实是最快的可能性，并且以n+1=O（n）的复杂度执行。但它假设你完美地记住了所有模式……在实践中，情况并非如此，我的个人经验是，有时你在第一次尝试时找不到匹配的对：

1. 把所有的袜子都扔到桌子上（1）
2. 剩下的袜子（n/2）：
   1. 随便拿一只袜子（1）
   2. 如果不是配对（1/P）：
      1. 找到类似图案的袜子
      2. 拿袜子比较（1）
      3. 如果OK，商店配对

现在这取决于我们找到匹配袜子的能力。如果你有一双深色/灰色或白色的运动袜，它们的图案通常非常相似，这一点尤其如此！让我们承认你找到相应袜子的概率为P。在找到相应的袜子形成一双之前，你平均需要1/P次尝试。整体复杂性为1+（n/2）*（1+1/P）=O（n）。

两者在袜子数量上都是线性的，并且是非常相似的解决方案。让我们稍微修改一下这个问题，承认你在集合中有多双相似的袜子，并且它是轻松存储多双袜子在一个动作（1+ε）。对于K个不同的模式，你可以实现：

1. 对于每只袜子（n）：
   1. 随便拿一只袜子（1）
   2. 把它放在模式的集群上
2. 对于每个集群（K）：
   1. 采取集群和存储袜子对（1+ε）

整体复杂度变成n+K=O（n）。它仍然是线性的，但是选择正确的算法现在可能在很大程度上取决于P和K的值！但是有人可能会再次反对，你可能很难为每只袜子找到（或创建）集群。

此外，您还可以通过查看网站上最好的算法并提出自己的解决方案来节省时间：）

排序的问题0.在你把它们扔进1号洗衣店之前，你把左边的线穿到右边。把它们拿出来，你剪断线，把每一对放在抽屉里——对n对进行2次操作，所以O（n）。

现在下一个问题是，你是否自己洗衣服，你妻子洗她的衣服。这可能是一个0的问题。：）

当我对袜子进行分类时，我做了一个近似的基数排序，将袜子放在相同颜色/图案类型的其他袜子附近。除了在我即将放下袜子的位置/附近看到完全匹配的情况外，我在那个点提取袜子。

几乎所有其他算法（包括USR评分最高的答案）都进行排序，然后删除对。我发现，作为一个人类，最好将一次考虑的袜子数量最小化。

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

1. 挑选一只与众不同的袜子（不管是什么先引起我的注意）。
2. 从该概念位置开始基数排序，根据与该位置的相似性从堆中取出袜子。
3. 把新袜子放在当前的袜子堆附近，距离根据袜子堆的不同而定。如果你发现自己把袜子放在另一只袜子的上面，因为它是相同的，在那里形成一对，然后取下它们。这意味着将来的比较不需要那么费力就能找到正确的位置。

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

通过首先拉动独特的袜子，您可以留出空间来“放大”不那么独特的特征。

在去掉荧光色、条纹袜子和三双长袜后，你可能最终会得到大部分白色袜子，大致按照它们的磨损程度排序。

在某些时候，袜子之间的差异足够小，其他人不会注意到差异，并且不需要任何进一步的匹配努力。

我刚刚完成了我的袜子配对，我发现最好的方法是这样做：

• 选择其中一只袜子并将其收起（为该双袜子创建一个“桶”）
• 如果下一个是前一个的对，则将其放入现有存储桶，否则创建一个新存储桶。

在最坏的情况下，这意味着你将有n/2个不同的桶，你将有n-2个关于哪个桶包含当前袜子对的确定。显然，如果你只有几对，这个算法效果很好；我用12对做了。

它不是很科学，但它工作得很好：）

拿起第一只袜子，放在桌子上。现在再拿一只袜子；如果它和第一只袜子匹配，把它放在第一只袜子的上面。如果不匹配，把它放在离第一只袜子稍远的桌子上。再拿第三只袜子；如果它和前两只袜子匹配，把它放在上面，或者把它放在离第三只袜子稍远的地方。重复，直到你把所有的袜子都捡起来。

我注意到所有的答案都忽略了这样一个事实，即有两点你可以执行预处理，而不会减慢你的整体洗衣性能。

此外，我们不需要假设有大量的袜子，即使是对大家庭来说也是如此。袜子从抽屉里拿出来，穿过，然后被扔在一个地方（也许是垃圾箱），在被清洗之前它们会呆在那里。虽然我不会把这个垃圾箱称为LIFO堆栈，但我想说可以肯定的是

1. 人们把两只袜子大致扔在同一区域bin，
2. 垃圾箱在任何时候都不是随机的，因此
3. 从这个bin顶部获取的任何子集通常都包含一双袜子。

由于我所知道的所有洗衣机的尺寸都是有限的（不管你要洗多少袜子），而且实际的随机化发生在洗衣机中，不管我们有多少袜子，我们总是有一些几乎不包含单例的小子集。

我们的两个预处理阶段是“将袜子放在晾衣绳上”和“从晾衣绳上取出袜子”，这是我们必须做的，以便获得不仅干净而且干燥的袜子。与洗衣机一样，晾衣绳是有限的，我假设我们有将袜子放在视线内的整个生产线。

下面是put_socks_on_line（）的算法：

while (socks left in basket) {take_sock();if (cluster of similar socks is present) {Add sock to cluster (if possible, next to the matching pair)} else {Hang it somewhere on the line, this is now a new cluster of similar-looking socks.Leave enough space around this sock to add other socks later on}}

不要浪费时间移动袜子或寻找最佳匹配，这一切都应该在O（n）中完成，我们还需要将它们放在未排序的线上。袜子还没有配对，我们在线上只有几个相似性簇。这里我们有一组有限的袜子是有帮助的，因为这有助于我们创建“好”的集群（例如，如果袜子集中只有黑色袜子，那么按颜色聚类就不是办法）

下面是take_socks_from_line（）的算法：

while(socks left on line) {take_next_sock();if (matching pair visible on line or in basket) {Take it as well, pair 'em and put 'em away} else {put the sock in the basket}

我应该指出，为了提高剩余步骤的速度，明智的做法是不要随机挑选下一只袜子，而是从每个集群中依次取出袜子。这两个预处理步骤都不会花费更多的时间，而不仅仅是把袜子放在线上或篮子里，无论如何我们都必须这样做，所以这应该会大大提高洗衣性能。

之后，很容易做哈希划分算法。通常，大约75%的袜子已经配对，给我留下了一个非常小的袜子子集，这个子集已经（有些）聚类了（在预处理步骤之后，我没有在我的篮子中引入太多熵）。另一件事是剩余的集群往往足够小，可以一次处理，所以有可能从篮子中取出整个集群。

下面是sort_remaining_clusters（）的算法：

while(clusters present in basket) {Take out the cluster and spread itProcess it immediatelyLeave remaining socks where they are}

这就是我将以前未配对的袜子引入系统并在没有任何特殊算法的情况下处理剩余袜子的地方-剩余的袜子非常少，并且可以在视觉上非常快速地处理。

对于所有剩余的袜子，我假设它们的对应物仍然没有洗，并将它们放在下一次迭代中。如果您随着时间的推移记录到未配对袜子的增长（“袜子泄漏”），您应该检查您的垃圾箱-它可能会被随机分配（您有猫睡在那里吗？）

我知道这些算法需要很多假设：一个作为某种LIFO堆栈的垃圾箱，一个有限的、正常的洗衣机，以及一个有限的、正常的晾衣绳——但这仍然适用于大量的袜子。

关于并行：只要你把两只袜子扔进同一个垃圾箱，你就可以轻松地并行化所有这些步骤。

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

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

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

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 pairsk: number of colorsC: sync overhead

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

我发现将分类过程整合到悬挂晾干中变得轻而易举。无论如何，我都需要拿起每只袜子，并将其悬挂（移动），并且将其挂在字符串上的特定位置几乎不需要花费任何费用。现在只是为了不强制搜索整个缓冲区（字符串），我选择按颜色/阴影放置袜子。左边更暗，右边更亮，前面更丰富多彩等。现在，在我挂起每只袜子之前，如果已经有匹配的袜子，我会查看它的“右附近”-这将“扫描”限制为2-3只其他袜子-如果是，我会将另一只挂在它旁边。然后我把它们卷成对，同时从绳子上取下，干燥时。

这可能看起来与顶部答案所建议的“按颜色形成堆栈”没有什么不同，但首先，不选择离散的堆栈，而是选择范围，我对“紫色”是“红色”还是“蓝色”堆栈进行分类没有问题；它只是介于两者之间。然后通过整合两个操作（挂起晾干和排序），挂起时排序的开销大约是单独排序的10%。

我的解决方案并不完全符合您的要求，因为它正式需要O(n)“额外”空间。然而，考虑到我的条件，它在我的实际应用中非常有效。因此，我认为它应该很有趣。

与其他任务相结合

我的特殊情况是，我不用烘干机，只是把我的布料挂在普通的烘干机上。挂布料需要O(n)操作（顺便说一句，我在这里总是考虑箱包装问题），这个问题本质上需要线性的“额外”空间。当我从桶里拿一只新袜子时，如果这双袜子已经挂好了，我会试着把它挂在它的旁边。如果是一双新袜子，我会在它旁边留一些空间。

Oracle机器更好；-）

显然需要一些额外的工作来检查是否有匹配的袜子已经挂在某个地方，并且它将呈现计算机的系数约为1/2的解决方案O(n^2)。但在这种情况下，“人为因素”实际上是一个优势-我通常可以很快（几乎O(1)）识别匹配的袜子是否已经挂起（可能涉及一些难以察觉的大脑缓存）-认为它是一种有限的“预言”，如oracleMachine；-）我们人类在某些情况下比数字机器具有这些优势；-）

几乎O(n)！

因此，将袜子配对问题与挂布问题联系起来，我免费获得O(n)“额外空间”，并且有一个关于O(n)时间的解决方案，只需要比简单的挂布多一点的工作，并且即使在非常糟糕的星期一早上也可以立即访问完整的袜子…；-）

你试图解决错误的问题。

解决方案1：每次你把脏袜子放进洗衣篮时，把它们打成一个小结。这样你就不必在洗涤后进行任何分类。把它想象成在Mongo数据库中注册索引。未来节省一些CPU的工作。

解决方案2：如果是冬天，你不必穿配套的袜子。我们是程序员。没有人需要知道，只要它有效。

解决方案3：分散工作。你想在不阻塞UI的情况下异步执行如此复杂的CPU进程。把那堆袜子塞进一个袋子里。只有在你需要的时候才找一双。这样它所花费的工作量就不那么明显了。

希望这有帮助！

从一堆袜子到袜子配对的高效算法

先决条件

1. 那堆袜子里至少得有一只
2. 桌子必须足够大以容纳N/2袜子（最坏的情况），其中N是总数袜子。

算法

尝试：

1. 挑第一只袜子
2. 把它放在桌子上
3. 挑选下一只袜子，看看它（可能会抛出“没有更多的袜子在堆里”例外）
4. 现在扫描桌子上的袜子（如果桌子上没有袜子，则抛出异常）
5. 有火柴吗？a）yes=>从表中删除匹配的袜子b）no=>把袜子放在桌子上（可能抛出'桌子不够大'异常）

除了：

• 表不够大：
  小心地将所有未配对的袜子混合在一起，然后恢复操作
     //此操作将产生一个新桩和一个空表

• 桌子上没有袜子：
     扔（最后一只不能换的袜子）

• 没有袜子留在堆里：
     出口洗衣房

最后：

• 如果一堆里还有袜子：
     goto 3

已知问题

算法将进入一个无限循环，如果周围没有表或桌子上没有足够的地方容纳至少一只袜子。

可能的改进

根据要排序的袜子数量，吞吐量可能是通过整理桌子上的袜子来增加，只要有足够的空间。

为了使其工作，需要一个具有唯一属性的属性每双袜子的值。这样的属性可以很容易地从袜子的视觉属性合成。

按所述属性对表上的袜子进行排序。让我们称该属性为将袜子排成一排，然后将深色的袜子放在右边（即push_back（））和左边颜色较浅的袜子（即。.push_front（））

对于巨大的桩，特别是以前看不见的袜子，属性合成可能需要大量时间，因此吞吐量显然会降低。但是，这些属性可以保存在内存中并重用。

需要一些研究来评估这种可能的效率问题如下：

• 使用上述方法配对的袜子的最佳数量是多少改善？
• 对于给定数量的袜子，之前需要多少次迭代吞吐量增加？
  a）最后一次迭代
  b）对于所有迭代

PoC符合MCVE指南：

#include <iostream>#include <vector>#include <string>#include <time.h>
using namespace std;
struct pileOfsocks {pileOfsocks(int pairCount = 42) :elemCount(pairCount<<1) {srand(time(NULL));socks.resize(elemCount);
vector<int> used_colors;vector<int> used_indices;
auto getOne = [](vector<int>& v, int c) {int r;do {r = rand() % c;} while (find(v.begin(), v.end(), r) != v.end());v.push_back(r);return r;};
for (auto i = 0; i < pairCount; i++) {auto sock_color = getOne(used_colors, INT_MAX);socks[getOne(used_indices, elemCount)] = sock_color;socks[getOne(used_indices, elemCount)] = sock_color;}}
void show(const string& prompt) {cout << prompt << ":" << endl;for (auto i = 0; i < socks.size(); i++){cout << socks[i] << " ";}cout << endl;}
void pair() {for (auto i = 0; i < socks.size(); i++) {std::vector<int>::iterator it = find(unpaired_socks.begin(), unpaired_socks.end(), socks[i]);if (it != unpaired_socks.end()) {unpaired_socks.erase(it);paired_socks.push_back(socks[i]);paired_socks.push_back(socks[i]);}elseunpaired_socks.push_back(socks[i]);}
socks = paired_socks;paired_socks.clear();}
private:int elemCount;vector<int> socks;vector<int> unpaired_socks;vector<int> paired_socks;};
int main() {pileOfsocks socks;
socks.show("unpaired socks");socks.pair();socks.show("paired socks");
system("pause");return 0;}