成本：移动袜子->高，查找/搜索袜子排成一排->小

我们想做的是减少移动次数，并用搜索次数进行补偿。此外，我们还可以利用智人的多威胁环境，在解密缓存中保存更多的东西。

X=您的，Y=您的配偶

从所有袜子的A堆开始：

选择两个袜子，将相应的X袜子放在X线上，将Y袜子放在Y线上的下一个可用位置。

直到A为空。

对于每行X和Y

选择行中的第一只袜子，沿着行搜索，直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时，当前正在查看的袜子与之前的袜子相同，请对这些袜子执行步骤2。

可选地，在第一步中，您从该行中拾取两个袜子，而不是两个，因为缓存内存足够大，我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，那么考虑到受试者的记忆足够大，你可以同时解析三只袜子。

直到X和Y都为空。

Done

然而，由于这与选择排序具有相似的复杂性，由于I/O（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。

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

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

案例1：所有袜子都是一样的（顺便说一句，这是我在现实生活中所做的）。

选择其中的任意两个组成一对。恒定时间。

案例2：有固定数量的组合（所有权、颜色、大小、纹理等）。

使用基数排序。这只是线性时间，因为不需要比较。

情况3：组合的数量事先未知（一般情况）。

我们必须进行比较，以检查两只袜子是否成对。选择基于O（n log n）比较的排序算法之一。

然而，在现实生活中，当袜子的数量相对较少（恒定）时，这些理论上的优化算法将无法很好地工作。这可能比顺序搜索花费更多的时间，理论上需要二次时间。

一种有效的袜子配对算法

前提条件

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

算法

Try:

挑选第一只袜子把它放在桌子上选择下一只袜子，然后看看它（可能会把“不再有袜子”扔到袜子堆里）现在扫描桌子上的袜子（如果桌子上没有袜子，则抛出异常）有匹配的吗？a） 是=>从桌子上取下匹配的袜子b） no=>将袜子放在桌子上（可能会抛出“桌子不够大”异常）

除了：

桌子不够大：小心地将所有未配对的袜子混合在一起，然后继续操作//此操作将导致一个新的堆和一个空表桌子上没有袜子：扔（最后一只不受欢迎的袜子）堆里没有袜子：出口洗衣房

最后：

如果袜子堆里还有袜子：转到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;
}

List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

当我对袜子进行排序时，我会进行近似基数排序，将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近，我能看到一对完全匹配的袜子，否则我会在那一刻取出这双袜子。

几乎所有其他算法（包括usr评分最高的答案）排序，然后删除配对。我发现，作为一个人，一次考虑的袜子数量最好尽量减少。

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

挑选一只与众不同的袜子（在袜子堆里最先映入我眼帘的东西）。从概念位置开始基数排序，根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近，距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面，因为它是相同的，请在那里形成一对，然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。

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

通过先穿上与众不同的袜子，你可以留出空间来“放大”那些不那么与众不同的特征。

在去除了浅色、条纹袜子和三双长袜之后，你可能最终会得到大致按磨损程度分类的白色袜子。

在某种程度上，袜子之间的差异很小，以至于其他人不会注意到差异，因此不需要进一步的匹配。