昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。

作为一名计算机科学家,我在想我能做什么?排序(根据大小/颜色/…)当然是为了实现O(NlogN)解决方案。

哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。

因此,问题基本上是:

给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)

我将感谢回答以下方面的问题:

大量袜子的一般理论解。袜子的实际数量没有那么多,我不相信我的配偶和我有超过30双。(而且很容易区分我的袜子和她的袜子;这也可以用吗?)它是否等同于元素清晰度问题?


当前回答

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

机器

机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的(希望是;-)。

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

然而,机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。

因此,根据之前的分析,应按降序使用以下操作:

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

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

算法

我的建议是:

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从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只袜子是否属于同一对。这可能在每种情况下都不可行。

其他回答

我所做的就是拿起第一只袜子,把它放下(比如,放在洗衣碗的边缘)。然后我拿起另一只袜子,检查它是否与第一只袜子相同。如果是,我会把它们都去掉。如果不是,我把它放在第一只袜子旁边。然后我拿起第三只袜子,将其与前两只袜子进行比较(如果它们还在的话)。等

这种方法可以很容易地在阵列中实现,假设“移除”袜子是一个选项。实际上,你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序(见下文),那么您只需移动它们,就可以得到一个数组,该数组中所有袜子都成对排列。

假设袜子的唯一操作是比较相等,这个算法基本上仍然是n2算法,尽管我不知道平均情况(从未学会计算)。

当然,分类可以提高效率,尤其是在现实生活中,你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中,树也可以做到这一点,但这是额外的空间。当然,我们又回到了NlogN(或者更多,如果有几只袜子按排序标准是相同的,但不是来自同一双)。

除此之外,我想不出什么,但这种方法在现实生活中似乎非常有效

这个问题实际上很有哲理。本质上,这是关于人们解决问题的能力(我们大脑的“湿件”)是否等同于算法所能完成的任务。

袜子分类的一个明显算法是:

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双,这是最佳的。总订单标签允许您使用标准哈希来获得与人工或硬件计算机相同的结果。

这是基于比较的模型中的Omega(n log n)下限。(唯一有效的操作是比较两只袜子。)

假设你知道你的2n只袜子是这样排列的:

p1 p2 p3。。。pn pf(1)pf(2)。。。功率因数(n)

其中f是集合{1,2,…,n}的未知排列。知道这一点不会使问题变得更难。有n个!可能的输出(上半部分和下半部分之间的匹配),这意味着您需要log(n!)=Omega(n log n)比较。这可通过分类获得。

由于您对元素区别性问题的连接感兴趣:证明元素区别性的Omega(n log n)界限比较困难,因为输出是二进制的yes/no。这里,输出必须是匹配的,并且可能输出的数量足以获得一个合适的界限。然而,有一个变量与元素的区别有关。假设你有2n只袜子,想知道它们是否可以唯一配对。您可以通过将(a1,a2,…,an)发送到(a1,a1,a2、a2,…、an,an)来获得ED的缩减。(附带地,通过拓扑结构,ED的硬度证明非常有趣。)

我认为,如果只允许等式测试,那么原始问题应该有一个Omega(n2)边界。我的直觉是:考虑一个测试后添加边的图形,并认为如果图形不密集,则输出不是唯一确定的。

你试图解决错误的问题。

解决方案1:每次你把脏袜子放进洗衣篮时,把它们打个小结。这样你就不用在洗完衣服后做任何分类了。把它想象成在Mongo数据库中注册索引。未来需要做一些工作来节省CPU。

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

解决方案3:分散工作。您希望异步执行如此复杂的CPU进程,而不阻塞UI。把那堆袜子塞进袋子里。只有在你需要的时候才找一双。这样,你的工作量就不那么明显了。

希望这有帮助!

一种有效的袜子配对算法

前提条件

堆里必须至少有一只袜子桌子必须足够大,以容纳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;
}