昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
我刚刚完成袜子配对，我发现最好的方法是：
选择一只袜子并将其收起来（为这双袜子创建一个“水桶”）如果下一个是上一个的一对，则将其放到现有的存储桶中，否则创建一个新的存储桶。
在最坏的情况下，这意味着您将有n/2个不同的存储桶，并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然，如果你只有几对，这个算法会很好地工作；我用了12双鞋。
它不是那么科学，但它工作得很好：）
其他回答
做一些预处理怎么样？我会在每只袜子上缝上一个标记或身份证号码，这样每双袜子都有相同的标记/身份证号码。这个过程可能在你每次买一双新袜子时都会完成。然后，您可以进行基数排序以获得O（n）总成本。为每个标记/身份证号码找一个位置，只需逐一挑选所有袜子并将它们放在正确的位置。
为了说明从一堆袜子中配对有多有效，我们必须首先定义机器，因为配对不是通过图灵或随机存取机器完成的，而随机存取机器通常用作算法分析的基础。
机器
机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的（希望是；-）。
我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制，由手臂或眼睛执行的操作具有非恒定的时间复杂性。这是因为我们不能用手臂移动一大堆无穷无尽的袜子，也不能用眼睛看到一大堆袜子上的袜子。
然而，机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。
因此，根据之前的分析，应按降序使用以下操作：
逻辑和算术运算环境读数环境改造
我们还可以利用这样一个事实，即人们只有非常有限的袜子。因此，环境改造可能涉及到所有袜子。
算法
我的建议是：
把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从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只袜子是否属于同一对。这可能在每种情况下都不可行。
案例1：所有袜子都是一样的（顺便说一句，这是我在现实生活中所做的）。
选择其中的任意两个组成一对。恒定时间。
案例2：有固定数量的组合（所有权、颜色、大小、纹理等）。
使用基数排序。这只是线性时间，因为不需要比较。
情况3：组合的数量事先未知（一般情况）。
我们必须进行比较，以检查两只袜子是否成对。选择基于O（n log n）比较的排序算法之一。
然而，在现实生活中，当袜子的数量相对较少（恒定）时，这些理论上的优化算法将无法很好地工作。这可能比顺序搜索花费更多的时间，理论上需要二次时间。
我提出的解决方案假设所有袜子在细节上都是相同的，除了颜色。如果袜子之间有更多的细节需要延迟，这些细节可以用来定义不同类型的袜子，而不是我的例子中的颜色。。
假设我们有一堆袜子，袜子可以有三种颜色：蓝色、红色或绿色。
然后，我们可以为每种颜色创建一个并行工作程序；它有自己的列表来填充相应的颜色。
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
这个问题实际上很有哲理。本质上，这是关于人们解决问题的能力（我们大脑的“湿件”）是否等同于算法所能完成的任务。
袜子分类的一个明显算法是：
Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
if s matches a sock t in N
remove t from N, bundle s and t together, and throw them in the basket
else
add s to N
现在这个问题的计算机科学都是关于步骤的
“如果s与N中的袜子t配对”。我们能多快“记住”到目前为止所看到的东西？“从N中删除t”和“将s添加到N”。跟踪我们目前所看到的情况有多贵？
人类将使用各种策略来实现这些目标。人类的记忆是关联的，类似于哈希表，其中存储值的特征集与相应的值本身配对。例如，“红色汽车”的概念映射到一个人能够记住的所有红色汽车。有完美记忆的人有完美的映射。大多数人（以及其他大多数人）在这方面都不完美。关联映射的容量有限。映射可能会在各种情况下（一杯啤酒太多）消失，被错误记录（“我认为她的名字是贝蒂，而不是内蒂”），或者即使我们观察到真相已经改变，也永远不会被覆盖（“爸爸的车”让人想起“橙色火鸟”，而我们实际上知道他用它换了红色的科迈罗）。
就袜子而言，完美回忆意味着看一只袜子总会产生它的同胞t的记忆，包括足够的信息（它在熨衣板上的位置），以便在恒定的时间内找到t。一个有照片记忆的人会在恒定的时间内完成1和2的任务。
记忆力不太好的人可能会根据自己能力范围内的特征使用一些常识等价类：尺寸（爸爸、妈妈、宝宝）、颜色（绿色、红色等）、图案（菱形、素色等）、风格（脚、膝盖高等）。这通常允许通过内存在恒定时间内定位类别，但随后需要通过类别“桶”进行线性搜索。
一个完全没有记忆或想象力的人（抱歉）只会把袜子放在一堆里，然后对整堆袜子进行线性搜索。
一个整洁的怪人可能会像某人建议的那样使用数字标签。这打开了完全排序的大门，允许人类使用与CPU完全相同的算法：二进制搜索、树、散列等。
因此，“最佳”算法取决于运行该算法的湿软件/硬件/软件的质量，以及我们是否愿意通过对其施加总订单来“欺骗”。当然，一个“最好”的元算法是雇佣世界上最好的袜子分类器：一个人或机器可以通过不断的时间查找、插入和删除，在1-1关联存储器中获取并快速存储大量的袜子属性集N。这样的人和机器都可以采购。如果你有一双袜子，你可以在O（N）时间内将所有袜子配对N双，这是最佳的。总订单标签允许您使用标准哈希来获得与人工或硬件计算机相同的结果。
