那么在处理之前做些什么？可以在每只袜子上缝上标记或ID号码，以便每对袜子都有相同的标记/ID号码。每次购买新袜子时都可以进行此过程。然后，您可以进行基数排序以获得O（n）的总成本。找到每个标记/ ID号码的位置，然后逐一选择所有袜子并将它们放入正确的位置。

我在攻读计算机科学博士期间经常思考这个问题。我提出了多种解决方案，取决于区分袜子并尽快找到正确配对的能力。
假设查看袜子并记住它们的独特图案的成本可以忽略不计（ε）。那么最好的解决方案就是把所有袜子都扔在桌子上。这包括以下步骤：
1. 把所有袜子都扔在桌子上（1），并创建一个哈希映射{图案：位置}（ε）。 2. 当还有剩余袜子（n/2）时：
- 随机挑选一只袜子（1） - 找到相应袜子的位置（ε） - 取出袜子（1）并存储配对
这确实是最快的方法，复杂度为 n + 1 = O(n)。但是它假定您完美地记住了所有图案...实际情况并非如此，我的个人经验是有时第一次尝试时找不到匹配的袜子：
1. 把所有袜子都扔在桌子上（1）。 2. 当还有剩余袜子（n/2）时：
- 随机挑选一只袜子（1） - 当它没有配对时（1/P）：
- 找到具有相似图案的袜子 - 取出袜子并比较（1） - 如果匹配，存储配对
现在这取决于我们找到匹配袜子的能力。如果您有深色/灰色配对或经常具有非常相似图案的白色运动袜！假设您有概率 P 找到相应袜子。平均需要 1/P 次尝试才能找到相应袜子形成一对。总复杂度为 1 + (n/2) * (1 + 1/P) = O(n)。
两种方法都是线性的，并且非常相似。让我们稍微修改问题，假设您拥有多对相似袜子，并且很容易在一次移动中存储多对袜子（1+ε）。对于 K 种不同的图案，您可以实施以下操作：
1. 对于每个袜子（n）：
- 随机挑选一只袜子（1） - 把它放在其图案簇上
2. 对于每个簇（K）：
- 取出簇并存储袜子的配对（1+ε）
总体复杂度变为 n+K=O(n)。它仍然是线性的，但是选择正确的算法现在可能会极大地取决于 P 和 K 的值！但是又有人可能会反对，您可能难以找到（或创建）每个袜子的簇。
此外，您还可以通过查看网站了解最佳算法并提出自己的解决方案来浪费时间 :)

许多作者指出，基数排序是一种有效的袜子排序方法。尚未提出完美的哈希方法。使用每双袜子购买的时间作为哈希是一种方法。只需按顺序编号袜子，随着购买，您可以将它们放入自己编号的抽屉中，以便在整理堆时更容易找到它们。
以下是24双袜子的示例。请注意，更大的袜子隔层消除了卷起袜子的需要，这被称为速度/存储权衡。

朝着从一堆袜子中高效配对算法迈进

前提条件

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

算法

尝试:

1. 拿第一只袜子
2. 把它放在桌子上
3. 拿下一只袜子，并看一看它（如果没有更多袜子则会抛出"堆里没有更多的袜子"异常）
4. 现在扫描桌子上的袜子（如果桌子上没有袜子则抛出异常）
5. 有配对吗？ a) 是 => 从桌子上移除匹配的袜子 b) 否 => 把袜子放在桌子上（可能会抛出"桌子不够大"的异常）

除外:

• 桌子不够大:
     小心翼翼地混合所有未配对的袜子，然后恢复操作
     // 这个操作将导致一个新的堆和一个空桌子

• 桌子上没有袜子了:
     抛出（最后一只无法配对的袜子）

• 堆里没有袜子了:
     退出洗衣房

最后:

• 如果堆里仍有袜子：
     转到3号步骤

已知问题

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

可能的改进

根据要排序的袜子数量，可以通过在桌子上排序袜子来提高吞吐量，前提是有足够的空间。

为了让这个方法起作用，需要一个属性，它对每一双袜子都有一个唯一的值。这样的属性可以从袜子的视觉属性中轻松地合成。

按照该属性对桌子上的袜子进行排序。我们称这个属性为“颜色”。把袜子排成一行，把颜色深的袜子放在右边（即.push_back()），把颜色浅的袜子放在左边（即.push_front()）。

对于巨大的堆和尤其是之前未见过的袜子，属性合成可能需要很长时间，因此吞吐量显然会降低。然而，这些属性可以持久化在内存中并重复使用。

需要一些研究来评估这种可能的改进的效率。以下问题出现了:

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

根据MCVE指南，提供相应的PoC：

#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]);
            }
            else
                unpaired_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;
}

两种思路：一种是寻找任何匹配的速度，另一种是寻找所有匹配的速度与存储空间的比较。

对于第二种情况，我想指出一个GPU并行版本，它查询所有匹配的袜子。

如果您有多个属性需要匹配，可以利用分组元组、更高级的zip迭代器和thrust的转换函数。为了简单起见，这里提供了一个简单的基于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毫秒

我的解决方案假设所有袜子在细节上都是相同的，除了颜色。如果有更多的细节可以区分袜子，则可以使用这些细节来定义不同类型的袜子，而不是像我的例子中一样使用颜色。
假设我们有一堆袜子，袜子可以有三种颜色：蓝色、红色或绿色。
然后，我们可以为每种颜色创建一个并行工作线程；它有自己的列表来填充相应的颜色。

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

Defant & Kravitz（1）提供了一种通过将袜子顺序穿脱在脚上进行分类的算法。 {{link1：}} 他们的算法适用于任意数量的脚。
{{link2：}} 该论文给出了一个定理（定理1.1），描述了可使用单只脚进行分类的袜子顺序。根据他们的定理1.3，每个具有4种颜色的袜子排序都可以使用最多两只脚进行分类，而存在着无法用两只脚分类的5种颜色的袜子排序。
参考文献： 1. Colin Defant和Noah Kravitz，《Foot-Sorting for Socks》（2022年）

如果你能将一双袜子的单个配对抽象为键本身和其它配对作为值，我们就可以利用哈希。

1. 在地板上为你和你的配偶各划出一个虚拟区域。

2. 从一堆袜子中取出一只。

3. 现在按照以下规则逐个将袜子放在地板上：

   • 识别袜子是你的还是她的，并查看地板上相应的区域。

   • 如果你能在地板上找到一双袜子，请将它们捆起来或夹起来，或者进行任何你发现一双袜子后会做的事情，并将其放入篮子中（从地板上移除）。

   • 将其放入相应的区域。

4. 重复步骤3，直到所有袜子都用完。

---

解释：

哈希和抽象

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

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

哈希或其他非就地解决方案不是选项，因为我无法复制我的袜子（尽管如果我能这样做，那将是很好的）。

我认为提问者考虑应用哈希，使得在放置它们之前应该知道任何一双袜子所属的插槽。

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

如何定义我们的哈希键？

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

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

Attribute[Gender] + Attribute[Colour] + Attribute[Material] + Attribute[Type1] + Attribute[Type2] + Attribute[Left_or_Right]

这是我们的第一个哈希函数。让我们使用一个简短的符号表示为h1(G_C_M_T1_T2_LR)。h1(x)不是我们的位置键。

另一个消除左右属性的哈希函数将是h2(G_C_M_T1_T2)。这第二个函数h2(x)是我们的位置键！（用于你身后地板上的空间）。

• 要定位插槽，请使用h2(G_C_M_T1_T2)。
• 一旦找到插槽，然后使用h1(x)检查它们的哈希值。如果它们不匹配，则您有一对。否则，将袜子扔进同一个插槽。

注意：由于我们在找到一对后会移除它，因此可以安全地假设最多只有一个具有唯一h2(x)或h1(x)值的插槽。

如果每只袜子都恰好有一双匹配的袜子，那么使用h2(x)来查找位置，如果没有成对的袜子，则需要检查，因为可以安全地假设它们是一双袜子。

在地板上放置袜子的重要性

让我们考虑一种情况，即把袜子堆叠在一起形成一堆（最坏情况）。这意味着我们别无选择，只能进行线性搜索以找到一双袜子。

将它们散落在地板上可提供更多的可见性，从而提高发现匹配袜子（与哈希密钥匹配）的机会。当一只袜子在第3步放在地板上时，我们的大脑下意识地记住了它的位置。 - 因此，在我们的记忆中如果存储了该位置，我们就可以直接找到匹配的一对袜子。 - 如果位置没有被记住，不用担心，我们仍然可以返回到线性搜索。

从地板上拿走匹配的一对袜子的重要性

• 短期人类记忆在要记住的项目较少时效果最好。因此，增加我们使用哈希来发现一对袜子的概率。
• 这也将减少在线性搜索袜子时需要搜索的项目数量。

分析

1. 情况1：当Derpina无法直接使用哈希技术去记住或找到地板上的袜子时，进行线性搜索。这不比遍历堆来寻找一对更糟。
   • 比较的上限：O(n^2)。
   • 比较的下限：(n/2)。 (当每另一只袜子Derpina拾起是前一只的一对时)。
2. 情况2：Derp记得他放在地板上每只袜子的位置，并且每只袜子都恰好有一对。
   • 比较的上限：O(n/2)。
   • 比较的下限：O(n/2)。

我所说的比较操作，从堆中取出袜子必然需要n次操作。因此，实际的下限将是n次迭代和n/2次比较。

加快速度

为了达到完美的分数，使得Derp能够进行O(n/2)次比较，我建议Derpina：

• 花更多的时间与袜子相处以熟悉它。是的，这意味着也要花更多的时间与Derp的袜子在一起。
• 玩像在网格中找对子这样的记忆游戏可以提高短期记忆表现，这可能非常有益。

这是否等同于元素唯一性问题？

我建议的方法是解决元素唯一性问题的方法之一，其中将它们放入哈希表并进行比较。

考虑到您的特殊情况只存在一个确切的配对，因此它已经非常等同于元素唯一性问题。因为我们甚至可以对袜子进行排序并检查相邻的袜子是否匹配（EDP的另一种解决方案）。

但是，如果给定袜子可能存在多个配对，则与EDP偏离。