昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
我在攻读计算机科学博士期间经常思考这个问题。我提出了多种解决方案，这取决于区分袜子的能力，从而尽可能快地找到正确的袜子。
假设看袜子和记住它们独特图案的成本可以忽略不计（ε）。那么最好的解决办法就是把所有的袜子都扔到桌子上。这包括以下步骤：
将所有袜子放在一张桌子上（1），并创建一个hashmap｛pattern:position｝（ε）当有剩余袜子时（n/2）：随机挑选一只袜子（1）查找相应袜子的位置（ε）取回袜子（1）并存放
这确实是最快的可能性，并且以n+1＝O（n）复杂度执行。但它假设你完全记得所有的模式。。。在实践中，情况并非如此，我个人的经验是，你有时在第一次尝试时找不到匹配的一对：
把所有袜子扔在桌子上（1）当有剩余袜子时（n/2）：随机挑选一只袜子（1）当未配对时（1/P）：找到具有相似图案的袜子拿袜子，比较两者（1）如果可以，存储配对
这现在取决于我们找到匹配对的能力。如果你的深色/灰色双鞋或白色运动袜经常有非常相似的图案，这一点尤其正确！让我们承认你有概率找到相应的袜子。在找到相应的袜子以形成一双袜子之前，平均需要1/P的尝试。总体复杂度为1+（n/2）*（1+1/P）=O（n）。
两者在袜子数量上都是线性的，并且是非常相似的解决方案。让我们稍微修改一下这个问题，承认你有多双类似的袜子，并且很容易在一次移动中存储多双袜子（1+ε）。对于K个不同的模式，您可以实现：
对于每只袜子（n）：随机挑选一只袜子（1）将其放到其模式的集群中对于每个集群（K）：取簇并储存袜子（1+ε）
总体复杂度变为n+K=O（n）。它仍然是线性的，但选择正确的算法现在可能很大程度上取决于P和K的值！但人们可能会再次反对，因为您可能很难找到（或创建）每只袜子的集群。
此外，你也可以在网站上查找最佳算法，并提出自己的解决方案，从而节省时间：）
其他回答
理论上的限制是O（n），因为你需要触摸每一只袜子（除非有些袜子已经配对）。
你可以用基数排序实现O（n）。你只需要为桶选择一些属性。
首先你可以选择（她的，我的）-把它们分成两堆，然后使用颜色（可以有任何颜色的顺序，例如按颜色名称的字母顺序）-按颜色将它们分成一堆（记住对同一堆中的所有袜子保持步骤1中的初始顺序），然后袜子的长度，然后是纹理，....
如果您可以选择有限数量的属性，但有足够多的属性可以唯一地标识每对属性，则应该使用O（k*n），如果我们可以考虑k是有限的，则使用O（n）。
我所做的就是拿起第一只袜子，把它放下（比如，放在洗衣碗的边缘）。然后我拿起另一只袜子，检查它是否与第一只袜子相同。如果是，我会把它们都去掉。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子，将其与前两只袜子进行比较（如果它们还在的话）。等
这种方法可以很容易地在阵列中实现，假设“移除”袜子是一个选项。实际上，你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序（见下文），那么您只需移动它们，就可以得到一个数组，该数组中所有袜子都成对排列。
假设袜子的唯一操作是比较相等，这个算法基本上仍然是n2算法，尽管我不知道平均情况（从未学会计算）。
当然，分类可以提高效率，尤其是在现实生活中，你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中，树也可以做到这一点，但这是额外的空间。当然，我们又回到了NlogN（或者更多，如果有几只袜子按排序标准是相同的，但不是来自同一双）。
除此之外，我想不出什么，但这种方法在现实生活中似乎非常有效
对于p双袜子（n=2p只袜子），我实际上是这样做的：
从袜子堆里随便拿一只袜子。对于第一只袜子，或者如果之前选择的所有袜子都已配对，只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子，请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时，可以将袜子分为普通类别或类型（白色/黑色、脚踝/圆领、运动型/连衣裙），并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配，把两只袜子放在一起，然后把它们从阵列中去掉。如果没有，请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。
这种方案的最坏情况是，每双袜子都不同，必须完全匹配，而且你挑选的第一双n/2袜子都不同。这是你的O（n2）场景，极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2，并且每种类型的袜子都足够相似（通常在穿着相关的术语中），使得该类型的任何袜子都可以与任何其他袜子配对，那么正如我上面所推断的，你必须与之进行比较的袜子的最大数量是t，之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生，并将最坏情况的复杂性降低到O（n*t），其中通常t<<n。
整理n双袜子的问题是O（n）。在你把它们扔进洗衣篮之前，你先把左边的衣服穿到右边的衣服上。取出时，你剪下线，把每一对线放进抽屉里——对n对线进行2次操作，所以O（n）。
现在，下一个问题很简单，你是自己洗衣服，还是妻子洗衣服。这可能是一个完全不同领域的问题。：）
两种思路，查找任何匹配项所需的速度，与查找所有匹配项所需要的速度相比，与存储相比。
对于第二种情况，我想指出一个GPU并行版本，它查询所有匹配的袜子。
如果您有多个要匹配的财产，则可以使用分组元组和更高级的zip迭代器以及推力的转换函数，尽管这里是一个基于GPU的简单查询：
//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>
// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator GpuListIterator;
template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
ColoredSockQuery( int colorToSearch )
{ SockColor = colorToSearch; }
int SockColor;
__host__ __device__
bool operator()(T x)
{
return x == SockColor;
}
};
struct GenerateRandomSockColor
{
float lowBounds, highBounds;
__host__ __device__
GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};
__host__ __device__
int operator()(const unsigned int n) const
{
thrust::default_random_engine rng;
thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
rng.discard(n);
return dist(rng);
}
};
template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
typedef typename std::iterator_traits<GpuListIterator>::value_type T;
std::cout << name << ": ";
thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
std::cout << "\n";
}
int main()
{
int numberOfSocks = 10000000;
GpuList socks(numberOfSocks);
thrust::transform(thrust::make_counting_iterator(0),
thrust::make_counting_iterator(numberOfSocks),
socks.begin(),
GenerateRandomSockColor(0, 200));
clock_t start = clock();
GpuList sortedSocks(socks.size());
GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
socks.end(),
sortedSocks.begin(),
ColoredSockQuery<int>(2));
clock_t stop = clock();
PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);
double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
std::cout << "Time elapsed in ms: " << elapsed << "\n";
return 0;
}
//nvcc -std=c++11 -o test test.cu
1000万只袜子的运行时间：9毫秒
