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

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

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

因此,问题基本上是:

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

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

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


当前回答

我刚刚完成袜子配对,我发现最好的方法是:

选择一只袜子并将其收起来(为这双袜子创建一个“水桶”)如果下一个是上一个的一对,则将其放到现有的存储桶中,否则创建一个新的存储桶。

在最坏的情况下,这意味着您将有n/2个不同的存储桶,并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然,如果你只有几对,这个算法会很好地工作;我用了12双鞋。

它不是那么科学,但它工作得很好:)

其他回答

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

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

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

算法答案:

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

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

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

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

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

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

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

我提出的解决方案假设所有袜子在细节上都是相同的,除了颜色。如果袜子之间有更多的细节需要延迟,这些细节可以用来定义不同类型的袜子,而不是我的例子中的颜色。。

假设我们有一堆袜子,袜子可以有三种颜色:蓝色、红色或绿色。

然后,我们可以为每种颜色创建一个并行工作程序;它有自己的列表来填充相应的颜色。

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

每当你拿起袜子时,把它放在一个地方。然后你拿起的下一只袜子,如果它与第一只袜子不匹配,就把它放在第一只袜子旁边。如果是,那就有一对。这样,有多少种组合其实并不重要,而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配,要么它没有匹配,这意味着你将它添加到数组中的一个位置。

这也意味着你几乎肯定不会把所有袜子都放在阵列中,因为袜子会在搭配时被取下。

一种有效的袜子配对算法

前提条件

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

袜子,无论是真的还是类似的数据结构,都将成对提供。

最简单的答案是,在允许袜子对分开之前,应该初始化袜子对的单个数据结构,该结构包含指向左右袜子的指针,从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。

这通过使用抽象层来消除任何计算配对问题。

将同样的想法应用于袜子配对的实际问题,显而易见的答案是:不要让你的袜子不配对。袜子是一双提供的,一双放在抽屉里(也许是把它们捆在一起),一双穿。但可能脱漆的地方是在洗衣机里,所以所需要的只是一个物理机制,让袜子保持在一起并有效地清洗。

有两种物理可能性:

对于一个“pair”对象,它保持指向每只袜子的指针,我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。

但是,为了让每一只袜子都能互相参照,有一个很好的解决方案:一个popper(如果你是美国人,可以使用“按扣”),比如:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

然后,你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起,再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。