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

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

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

因此,问题基本上是:

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

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

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


当前回答

你试图解决错误的问题。

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

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

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

希望这有帮助!

其他回答

作为实际解决方案:

快速制作一堆易于区分的袜子。(用颜色表示)快速整理每一堆,并使用袜子的长度进行比较。作为一个人,你可以很快地决定用哪只袜子进行分区,以避免最坏的情况。(你可以看到多只袜子平行排列,这对你有利!)当垃圾堆达到一个阈值时,停止分类,在该阈值下,您可以立即找到不合适的袜子和短袜

如果你有1000只袜子,有8种颜色,平均分布,你可以在c*n时间内每125只袜子做4堆。以5只袜子为阈值,你可以在6次跑步中对每一堆袜子进行分类。(数2秒把袜子扔到正确的堆上,只需要不到4小时。)

如果你只有60只袜子、3种颜色和2种袜子(你/你妻子的),你可以在1次跑步中对每一堆10只袜子进行分类(同样阈值=5)。(数2秒,需要2分钟)。

最初的桶排序将加快您的进程,因为它在c*n时间内将n个袜子分成k个桶,因此您只需执行c*n*log(k)工作。(不考虑阈值)。所以,你所做的所有关于n*c*(1+log(k))的工作,其中c是把袜子扔在一堆上的时间。

与任何c*x*n+O(1)方法相比,只要log(k)<x-1,该方法将是有利的。


在计算机科学中,这可能很有用:我们有一个n个事物的集合,它们的顺序(长度)和等价关系(额外的信息,例如袜子的颜色)。等价关系允许我们对原始集合进行分区,并且在每个等价类中我们的顺序仍然保持不变。一个事物到它的等价类的映射可以在O(1)中完成,因此只需要O(n)就可以将每个项分配给一个类。现在我们已经使用了额外的信息,可以以任何方式对每个类进行排序。其优点是数据集已经明显更小。

该方法也可以嵌套,如果我们有多个等价关系->使颜色堆积,而不是在纹理上的每个堆积分区内,而不是按长度排序。任何等价关系如果创建一个分区,其中包含2个以上的元素,且大小大致相等,那么与排序相比,排序的速度都会有所提高(前提是我们可以直接将袜子分配给它的堆),并且排序可以在较小的数据集上快速进行。

真实世界方法:

尽快将袜子从未分类的袜子堆中取出,一次一个,然后放在前面。桩应布置得有一定的空间效率,所有袜子指向相同的方向;桩的数量受你容易到达的距离的限制。选择一堆袜子时,应尽快将袜子放在一堆看起来很像的袜子上;偶尔出现的I型(把袜子放在不属于它的袜子堆上)或II型(当有一堆类似的袜子时,把袜子放进自己的袜子堆里)错误是可以容忍的——最重要的考虑是速度。

一旦所有袜子都成了一堆,快速穿过多个袜子堆,创建成对的袜子,然后将它们取下(这些袜子朝抽屉方向)。如果袜子堆中有不匹配的袜子,请将它们重新堆到最好的位置(在尽可能快的限制范围内)。当处理完所有的多袜子堆后,将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦,你完了——我有很多袜子,直到大部分都脏了才洗。另一个实际注意事项是:我将一双袜子的顶部翻转到另一双袜子上,利用它们的弹性财产,以便它们在被运送到抽屉和抽屉中时保持在一起。

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

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

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

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

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

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

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

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

非算法答案,但当我这样做时“高效”:

步骤1)丢弃所有现有袜子第2步)去沃尔玛买10-n包的白色和m包黑色。日常无需其他颜色生活

然而,有时,我不得不再次这样做(丢失的袜子、损坏的袜子等),我讨厌太频繁地丢弃完美的袜子(我希望他们继续出售相同的袜子参考!),所以我最近采取了不同的方法。

算法答案:

考虑一下,如果你只为第二叠袜子画一只袜子,就像你正在做的那样,你在天真的搜索中找到匹配袜子的几率很低。

所以,随机挑选其中五个,记住它们的形状或长度。

为什么是五?通常情况下,人类在工作记忆中记住五到七个不同的元素是很好的——有点像RPN堆栈的人类等价物——五个是安全的默认值。

从2n-5的堆栈中选择一个。现在,在你画的五个图案中寻找一个匹配(视觉模式匹配-人类擅长用一个小堆栈),如果你没有找到一个,那么把它添加到你的五个。继续从袜子堆中随机挑选袜子,并与你的5+1袜子进行比较。随着堆栈的增长,它会降低性能,但会提高赔率。快得多。

请随意写下公式,以计算50%的匹配几率需要抽取多少样本。IIRC这是一个超几何定律。

我每天早上都会这样做,很少需要三次以上的平局——但我有n双类似的m形白袜子(大约10双,不分输赢)。现在你可以估计我的股票堆的大小:-)

顺便说一句,我发现,每次我需要一双袜子时,整理所有袜子的交易成本之和远远少于一次整理和装订袜子。准时制的效果更好,因为这样你就不必绑袜子了,而且边际回报也在减少(也就是说,当你在洗衣店的某个地方时,你一直在寻找那两到三只袜子,而你需要完成袜子的搭配,而你却在这上面浪费了时间)。

一种有效的袜子配对算法

前提条件

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