如何有效地配对袜子?

dquis 发布于 2019-02-22 algorithm 最后更新 2019-02-22 13:26 158 浏览

昨天我把干净的洗衣店里的袜子做成了配对,并且发现我做这件事的方式效率不高。我在做一个天真的搜索 - 选择一只袜子并“迭代”一堆以找到它的一对。这要求平均迭代n / 2 * n / 4 = n 2 / 8袜子。 作为一名计算机科学家,我在想我能做什么?当然想到排序(根据大小/颜色/ ...)来实现O(NlogN)解决方案。 哈希或其他非原地解决方案不是一种选择,因为我无法复制我的袜子(尽管如果可以的话它可能会很好)。 所以,问题基本上是: 给定一堆n对袜子,其中包含2n元素(假设每个袜子只有一对配对),将它们有效配对到对数额外空间的最佳方法是什么? (如果需要,我相信我可以记住这些信息量。) 我将非常感谢解决以下问题的答案:

  • 大量袜子的一般理论解决方案。
  • 袜子的实际数量并不大,我不相信我的配偶和我有超过30双。 (我的袜子和她的袜子很容易分辨,这也可以用吗?)
  • 是否等同于element distinctness problem
已邀请:

zin

赞同来自:

两条思路,即查找任何匹配所需的速度,以及与存储相比查找所有匹配所需的速度。 对于第二种情况,我想指出一个gpu并行版本,它会查询所有匹配的袜子。 如果你有多个要匹配的属性,你可以使用分组元组和fancier zip迭代器以及推力的转换函数,为简单起见,尽管这是一个简单的基于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毫秒

nsit

赞同来自:

使用模式作为哈希,创建一个将用于不匹配的socks的哈希表。逐个迭代袜子。如果袜子在哈希表中具有模式匹配,则将袜子从表中取出并成对。如果袜子没有匹配,请将其放入表中。

dquia

赞同来自:

作为一个实际解决方案

  1. 快速制作成堆易于辨别的袜子。 (用颜色说)
  2. 每次打桩并使用袜子的长度进行比较。作为一个人,你可以做出一个相当快速的决定,哪个袜子用于分区,避免最坏的情况。 (您可以并行查看多个袜子,使用它们对您有利!)
  3. 当它们达到您可以立即找到现货对和无法使用的袜子的门槛时停止分拣
如果你有1000个袜子,8种颜色和平均分布,你可以在c * n时间内制作每堆125袜子4堆。使用5个袜子的阈值,您可以在6次运行中对每一堆进行排序。 (计算2秒钟在右侧桩上扔袜子,它将花费你不到4小时。) 如果你只有60只袜子,3种颜色和2种袜子(你/你的妻子),你可以在1次运行中对每堆10只袜子进行分类(再次阈值= 5)。 (计算2秒钟将需要2分钟)。 最初的存储桶排序会加快您的进程,因为它会将您的n个袜子划分为c*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个元素且具有大约均匀大小的分区的任何等价关系将带来比排序更快的速度提升(假设我们可以直接将袜子分配到其堆中),并且在较小的数据集上可以非常快速地进行排序。

wquod

赞同来自:

这个问题实际上是深刻的哲学。从本质上讲,人们解决问题的能力(我们大脑的“湿软件”)是否等同于算法可以实现的功能。 一种明显的袜子分类算法是:

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
现在这个问题的计算机科学就是关于步骤的
  1. “如果s与袜子t配对N”。我们能多快“记住”到目前为止看到的东西?
  2. “从N中删除t”和“将s添加到N”。跟踪到目前为止我们所看到的情况有多贵?
人类将使用各种策略来实现这些目标。 Human memory is associative,类似于哈希表,其中存储值的功能集与相应的值本身配对。例如,“红色汽车”的概念映射到一个人能够记住的所有红色汽车。拥有完美记忆的人有完美的映射。大多数人在这方面(以及大多数其他人)都不完美。关联映射的容量有限。在各种情况下(一个啤酒太多),映射可能会黯然失色,被记录错误(“我虽然她的名字是Betty,而不是Nettie”),或者即使我们观察到真相发生了变化也永远不会被覆盖(“爸爸的汽车“唤起”橙色火鸟“我们实际上知道他已经交换了红色Camaro”。 在袜子的情况下,完美的回忆意味着看着袜子s总是产生其兄弟t的记忆,包括足够的信息(它在熨衣板上)在恒定时间内定位t。具有照相记忆的人在不变的情况下在恒定时间内完成1和2。 记忆力不够完美的人可能会根据其追踪能力的特征使用一些常识等价类:大小(爸爸,妈妈,宝宝),颜色(绿色,红色等),图案(亚皆老街,平原等) ,风格(footie,knee-high等)。所以熨衣板将分为几类。这通常允许类别按存储器定位在恒定时间内,但是需要通过类别“桶”进行线性搜索。 没有记忆或想象力的人(对不起)只会把袜子放在一堆,并对整堆进行线性搜索。 一个整洁的怪物可能会像有人建议的那样使用数字标签。这为总排序打开了大门,允许人们使用与CPU相同的算法:二进制搜索,树,哈希等。 因此,“最佳”算法取决于运行它的湿件/硬件/软件的质量以及我们通过强制对订单进行“欺骗”的意愿。当然,一个“最好的”元算法是雇用世界上最好的袜子分类器:一个人或机器,可以在一个1-1的联想记忆中获取并快速存储大量的N组袜子属性集,并且具有恒定的时间查找,插入,并删除。这样的人和机器都可以采购。如果你有一个,你可以在O(N)时间内将所有袜子配对N对,这是最佳的。总订单标签允许您使用标准散列来获得与人机或硬件计算机相同的结果。

nin

赞同来自:

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);
  }
}

siure

赞同来自:

案例1:所有的袜子都是相同的(这就是我在现实生活中所做的事情)。 选择他们中的任何两个来做一对。恒定时间。 案例2:有一定数量的组合(所有权,颜色,大小,纹理等)。 使用radix sort。这只是线性时间,因为不需要比较。 案例3:预先不知道组合的数量(一般情况)。 我们必须进行比较以检查两只袜子是否成对。选择一个基于O(n log n)比较的排序算法。 然而在现实生活中,当袜子的数量相对较小(恒定)时,这些理论上最优的算法将不能很好地工作。它可能比顺序搜索花费更多的时间,这在理论上需要二次时间。

jenim

赞同来自:

从你的问题很清楚,你没有太多实际的洗衣经验:)。您需要一种适用于少量不可配对袜子的算法。 到目前为止,答案并没有充分利用我们的人类模式识别能力。 Set的游戏提供了如何做到这一点的线索:将所有袜子放在一个二维空间中,这样你就可以很好地识别它们,并用手轻松触及它们。这限制了你约120 * 80厘米左右的面积。从那里选择您识别的对并删除它们。将额外的袜子放在自由空间并重复。如果你为那些容易辨认的袜子(想念小子元素)的人洗手,你可以先选择那些袜子来做基数分类。该算法仅在单袜数较低时才有效

umodi

赞同来自:

拿起第一只袜子放在桌子上。现在选择另一只袜子;如果它与第一个选中的相匹配,则将其放在第一个上面。如果没有,请将它放在离第一个小距离的桌子上。选第三个袜子;如果它匹配前两个中的任何一个,将它放在它们之上,或者将它放在距离第三个的一小段距离。重复,直到你拿起所有的袜子。

bquia

赞同来自:

由于人脑的结构与现代CPU完全不同,这个问题没有实际意义。 人类可以通过“寻找匹配对”可以成为一个不太大的集合的一个操作来赢得CPU算法。 我的算法:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}
至少这是我在现实生活中使用的,我发现它非常有效。缺点是它需要一个平坦的表面,但它通常很丰富。

xporro

赞同来自:

内容太长未翻译

riure

赞同来自:

我的解决方案并不完全符合您的要求,因为它正式要求O(n)“额外”空间。但是,考虑到我的条件,它在我的实际应用中非常有效。因此我觉得它应该很有趣。

与其他任务结合 我的特殊情况是我不使用烘干机,只需将布挂在普通的布烘干机上。挂布需要O(n)操作(顺便说一句,我总是在这里考虑bin packing问题),问题本质上需要线性“额外”空间。当我从桶中取出一个新的袜子时,我试着把它挂在它的一对旁边,如果它已经挂了。如果它是一对新袜子,我会留下一些空间。

Oracle Machine更好; - ) 显然需要一些额外的工作来检查是否有匹配的袜子已经挂在某处,它会为计算机呈现O(n^2)系数大约为1/2的解决方案。但在这种情况下,“人为因素”实际上是一个优势 - 我通常可以很快(几乎O(1))识别匹配的袜子,如果它已经挂起(可能涉及一些难以察觉的脑内缓存) - 认为它是一种有限的“oracle”在Oracle Machine ;-)我们,在某些情况下,人类比数字机器具有这些优势;-)

几乎是O(n) 因此,将袜子配对问题与挂布问题联系起来我免费获得了O(n)“额外空间”,并且及时解决了O(n)的问题,只需要比简单的挂布更多的工作,并且可以立即访问完整的甚至在一个非常糟糕的星期一早上的袜子...... ;-)

ret

赞同来自:

现实世界的方法: 尽快将袜子从未分类的绒毛上取下,然后放在你面前的绒毛中。桩应安排在一定的空间效率,所有袜子指向相同的方向;桩的数量受到您可以轻松到达的距离的限制。选择要放袜子的绒毛应该 - 尽可能快 - 将袜子放在一堆明显像袜子上;偶尔的I型(将袜子放在它不属于的桩上)或II型(当有现成的袜子堆时,将袜子放在自己的桩中)可以容忍错误 - 最重要的考虑因素是速度。一旦所有的袜子堆成一堆,快速穿过多袜子堆创建成对并移除它们(这些正朝向抽屉)。如果堆中存在不匹配的袜子,则将它们重新堆叠到最佳状态(在尽可能快的约束范围内)堆中。当所有多袜子堆已经处理完毕时,匹配由于II型错误而未配对的剩余可配对袜子。哎呀,你已经完成了 - 我有很多袜子,直到很大一部分脏了才洗它们。另一个实用的注意事项:我将一双袜子的顶部翻过另一个,利用它们的弹性,使它们在被运送到抽屉和抽屉时保持在一起。

tut

赞同来自:

做一些预处理怎么样?我会在每个袜子上缝上一个标记或id号码,每一对都有相同的标记/ id号码。每次购买一双新袜子时都可以完成这个过程。然后,您可以执行radix sort以获得O(n)总成本。找到每个标记/身份证号码的位置,然后逐个挑选所有袜子并将它们放入正确的位置。

qenim

赞同来自:

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

  • 步骤1)丢弃所有现有袜子
  • 步骤2)转到Walmart并通过10-n包的数据包购买 白色和米包黑色。每天都不需要其他颜色 寿命。
然而有时候,我必须再次这样做(丢失袜子,损坏的袜子等),我不喜欢经常丢弃完美的袜子(我希望他们继续销售相同的袜子参考!),所以我最近采取了一种不同的方法。 算法答案: 考虑一下,如果你只为第二叠袜子画一个袜子,就像你在做的那样,你在天真的搜索中找到匹配的袜子的几率非常低。
  • 所以随意拿起其中的五个,并记住它们的形状或长度。
为什么五个?通常人类是好的记住工作记忆中的五到七个不同的元素 - 有点像人类相当于RPN堆栈 - 五是安全的默认值。
  • 从2n-5的堆叠中取出一个。
  • 现在寻找一个匹配(视觉模式匹配 - 人类擅长使用小筹码)在你画的五个内部,如果你没找到,然后将其添加到你的五个。
  • 随意从堆叠中挑选袜子并与您的5 + 1袜子进行比较。随着筹码的增长,它会降低你的表现,但会提高你的赔率。快得多。
随意记下公式,计算你必须抽取多少样本,以获得50%的匹配几率。 IIRC这是一个超几何定律。 我每天早上都这样做,很少需要超过三次抽奖 - 但是我有一些n类似的配对(大约10个,给予或带走丢失的)m形白色袜子。现在你可以估算一堆股票的大小:-) 顺便说一句,我发现每次需要一双袜子时,所有袜子的分拣交易成本总和远远低于做一次并绑定袜子。准时工作更好,因为那时你不必绑袜子,并且还有一个递减的边际收益(也就是说,你继续寻找那两个或三个袜子,当你在洗衣房的某个地方,你需要完成匹配你的袜子,你就失去了时间)。

uqui

赞同来自:

这就是我实际操作的方式,对于p双袜子(n = 2p个别袜子):

  • 从堆里随意拿一只袜子。
  • 对于第一只袜子,或者如果所有以前选择过的袜子已经配对,只需将袜子放入你面前未成对袜子“阵列”的第一个“槽”中。
  • 如果您有一个或多个选定的未配对袜子,请检查您当前的袜子是否与阵列中所有未配对的袜子有关。
    • 在构建阵列时,可以将袜子分成一般类别或类型(白色/黑色,脚踝/工作人员,运动/服饰),并“向下钻取”以仅比较类似的情况。
    • 如果找到可接受的匹配项,请将两个袜子放在一起并将其从阵列中移除。
    • 如果不这样做,请将当前袜子放入阵列中的第一个打开的插槽中。
  • 每只袜子重复一次。
这种方案最糟糕的情况是每双袜子都不同,必须完全匹配,而你挑选的前n / 2袜子都是不同的。这是你的O(n 2 )情景,而且极不可能。如果袜子t的独特类型的数量小于对的数量p = n / 2,并且每种类型的袜子足够相似(通常与穿着有关的术语),那么任何类型的袜子都可以与任何袜子配对另外,正如我上面推断的那样,你需要比较的袜子的最大数量是t,之后你拉的下一个袜子将匹配其中一个未配对的袜子。这种情况在平均袜子抽屉中比最坏情况更可能,并且将最坏情况复杂性降低到O(n * t),其中通常t <<< ñ。

tiste

赞同来自:

袜子,无论是真正的袜子还是一些类似的数据结构,都将成对供应。 最简单的答案是在允许分离对之前,该对的单个数据结构应该已经初始化,其中包含指向左右袜子的指针,从而使袜子能够直接或通过它们的对引用。袜子也可以扩展为包含指向其伙伴的指针。 这通过用抽象层去除它来解决任何计算配对问题。 将相同的想法应用于配对袜子的实际问题,明显的答案是:不要让你的袜子不配对。袜子作为一对提供,作为一对放入抽屉(也许通过将它们组合在一起),作为一对穿着。但是,可以在洗衣机中取消配对,所以所需要的只是一种物理机制,可以让袜子保持在一起并有效地洗涤。 有两种物理可能性: 对于保持指向每个袜子的指针的“对”对象,我们可以使用一个布袋来保持袜子在一起。这似乎是巨大的开销。 但是对于每个袜子来保持对另一个的引用,有一个简洁的解决方案:一个popper(或者如果你是美国人的'按钮'),例如: http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html 然后你所做的就是把你的袜子放在一起,然后把它们放在你的洗衣篮里,然后你再次解决了需要将袜子与“对”概念的物理抽象结合起来的问题。

uet

赞同来自:

这是在问错误的问题。要问的正确问题是,为什么我要花时间整理袜子?当您重视您选择的X货币单位的空闲时间时,每年的成本是多少? 通常情况下,这不仅仅是任何空闲时间,也就是早上的空闲时间,你可以在床上消费,或者喝着咖啡,或者早点离开并且不会被交通堵塞。 退一步往往是好事,并思考解决问题的方法。 还有一种方法! 找一个你喜欢的袜子。考虑所有相关特征:不同光照条件下的颜色,整体质量和耐久性,不同气候条件下的舒适度和气味吸收。同样重要的是,它们不应该在储存时失去弹性,因此天然织物是好的,它们应该用塑料包装。 如果左脚袜和右脚袜之间没有区别,那就更好了,但这并不重要。如果袜子是左右对称的,找到一对是O(1)操作,并且对袜子进行分类是近似O(M)操作,其中M是你家里的地方数量,你已经乱扔袜子,理想情况下是一些小的常数。 如果您选择左右袜子不同的花式配对,则对左右脚桶进行完整的铲斗排序需要O(N + M),其中N是袜子的数量,M与上述相同。其他人可以给出寻找第一对的平均迭代的公式,但是找到盲搜索对的最坏情况是N / 2 + 1,这对于合理的N来说变得天文数字不太可能。这可以通过使用高级图像来加速。识别算法和启发式,用Mk1 Eyeball扫描一堆未分类的袜子。 因此,实现O(1)袜子配对效率的算法(假设对称袜子)是:

  1. 您需要估计一生中需要多少双袜子,或者可能直到您退休并转移到温暖的气候而不需要再次穿袜子。如果你还年轻,你还可以估计在我们家里都有袜子分拣机器人之前需要多长时间,整个问题变得无关紧要。
  2. 您需要了解如何批量订购您选择的袜子,以及它的成本和交付量。
  3. 订购袜子!
  4. 摆脱旧袜子。
另一个步骤3将涉及比较多年来一次购买相同数量或许更便宜的袜子的成本,并增加分拣袜子的成本,但请相信我的话:批量购买更便宜!此外,存储袜子的价值以袜子价格通胀的速度增加,这比你在许多投资上获得的要多。然后还有存储成本,但袜子真的不占用衣柜顶层的空间。 问题解决了。所以,只要得到新的袜子,抛弃/捐赠你的旧袜子,并在知道你每天都在为你的余生节省金钱和时间之后过上幸福的生活。

qnon

赞同来自:

迈向一种有效​​的算法,用于配对袜子 前提条件
  1. 堆中必须至少有一个袜子
  2. 桌子必须足够大以容纳N / 2 袜子(最坏的情况),其中N是总数 袜子。
算法 尝试:
  1. 选择第一个袜子
  2. 把它放在桌子上
  3. 选择下一个袜子,看看它(可能会抛出“不再有袜子”)
  4. 现在扫描桌子上的袜子(如果桌子上没有袜子,则抛出异常)
  5. 有匹配吗? a)是=>从表中删除匹配的袜子 b)没有=>把袜子放在桌子上(可能会抛出'桌子不够大'的例外)
除:
  • 表格不够大:    
       小心地将所有未配对的袜子混合在一起,然后恢复操作  
        //此操作将导致新堆和空表
  • 桌子上没有袜子:   
        throw(最后一个无法使用的袜子)
  • 堆中没有袜子:   
       退出洗衣房
最后:
  • 如果堆里还有袜子:   
        goto 3
已知的问题    
如果周围没有表格,算法将进入无限循环    桌子上没有足够的空间容纳至少一个袜子。 可能的改进    
根据要分类的袜子数量,吞吐量可以是    如果足够的话,可以通过对桌子上的袜子进行分类来增加    空间。 为了使其工作,需要具有唯一性的属性    每双袜子的价值。这样的属性可以很容易    从袜子的视觉特性合成。 按所述属性对桌子上的袜子进行排序。我们称之为该属性    '颜色'。将袜子排成一排,并将深色袜子放入    右边(即.push_back())和左边较浅色的袜子(即    .push_front()) 对于巨大的桩,特别是以前看不见的袜子,属性合成    可能需要大量时间,因此吞吐量会明显减少。    但是,这些属性可以保留在内存中并重用。 需要进行一些研究来评估这种可能性的效率    改进。出现以下问题:
  • 使用上述配对的袜子的最佳数量是多少     改进?
  • 对于给定数量的袜子,之前需要多少次迭代     吞吐量增加?       
    a)最后一次迭代       
    b)对于所有迭代整体
PoC符合MCVE指南:
#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 =  {
         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;
}

overo

赞同来自:

在我的博士(计算机科学)期间,我经常讨论这个问题。我想出了多种解决方案,这取决于区分袜子的能力,从而尽可能快地找到正确的对。 假设看袜子和记忆他们的独特模式的成本可以忽略不计(ε)。那么最好的解决方案就是将所有袜子扔在桌子上。这包括以下步骤:

  1. 将所有袜子扔在桌子上(1)并创建一个散列图{pattern:position}(ε)
  2. 虽然有剩余的袜子(n / 2):
    1. 拿起一个随机袜子(1)
    2. 找到相应袜子的位置(ε)
    3. 检索袜子(1)和商店对
这确实是最快的可能性,并且以n + 1 = O(n)复杂度执行。但它假设您完全记住所有模式......在实践中,情况并非如此,我个人的经验是您有时在第一次尝试时找不到匹配对:
  1. 将所有袜子扔在桌子上(1)
  2. 虽然有剩余的袜子(n / 2):
    1. 拿起一个随机袜子(1)
    2. 虽然没有配对(1 / P):
      1. 找到类似模式的袜子
      2. 拿袜子比较两者(1)
      3. 如果可以,请存储对
这现在取决于我们找到匹配对的能力。如果您有深色/灰色对或白色运动袜通常具有非常相似的图案,则尤其如此!让我们承认你有P找到相应袜子的概率。在找到相应的袜子形成一对之前,你平均需要1 / P次尝试。总体复杂度为1 +(n / 2)*(1 + 1 / P)= O(n)。 两者都是袜子数量的线性,是非常相似的解决方案。让我们稍微修改一下这个问题,并承认你在套装中有多对类似的袜子,并且很容易在一次移动中存储多对袜子(1 +ε)。对于K个不同的模式,您可以实现:
  1. 每只袜子(n):
    1. 拿起一个随机袜子(1)
    2. 将它放在其模式的群集
  2. 对于每个群集(K):
    1. 选择群集并存储袜子对(1 +ε)
总体复杂度变为n + K = O(n)。它仍然是线性的,但选择正确的算法现在可能在很大程度上取决于P和K的值!但是,人们可能会再次反对您可能难以为每个袜子找到(或创建)群集。 此外,您还可以通过在网站上查看最佳算法并提出自己的解决方案来节省时间:)

paut

赞同来自:

成本:移动袜子 - >高,找到/搜索袜子 - >小 我们想要做的是减少移动次数,并根据搜索次数进行补偿。此外,我们可以利用智人的多线程环境在决策缓存中保存更多内容。 X =你的,Y =你的配偶 从所有袜子的堆A: 选择两个袜子,在X线上放置相应的X袜子,在下一个可用位置Y袜子放在Y线上。 直到A为空。 对于每一行X和Y.

  1. 选择第一个袜子,沿着线搜索,直到找到相应的袜子。
  2. 放入相应的成品袜子。
  3. 可选当您在搜索线时,您正在查看的当前袜子与之前相同,请为这些袜子执行第2步。
可选地,对于第一步,你从那条线而不是两条袜子中拿起两个袜子,因为缓存内存足够大,我们可以快速识别袜子是否与您正在观察的线上的当前袜子匹配。如果你有幸拥有三只手臂,你可以同时解析三只袜子,因为主体的记忆足够大。 直到X和Y都为空。 完成 然而,由于这与选择排序具有类似的复杂性,所以花费的时间远远少于I / O(移动袜子)和搜索(搜索线条的袜子)的速度。

fnam

赞同来自:

我推出了另一种解决方案,它不会承诺更少的操作,也不会减少耗时,但应该尝试看看它是否足够好,可以在大量的袜子配对中提供更少的时间消耗。 前提条件: 不能保证有相同的袜子。如果它们具有相同的颜色,则并不意味着它们具有相同的尺寸或图案。袜子随机洗牌。可能有奇数袜子(有些缺少,我们不知道有多少)。准备记住变量“index”并将其设置为0。 结果将有一两堆:1。“匹配”和2.“缺失” 启发式:

  1. 找到最有特色的袜子。
  2. 找到匹配。
  3. 如果没有匹配,请将其放在“丢失”的堆上。
  4. 从1开始重复,直到没有更独特的袜子。
  5. 如果少于6只袜子,请转到11。
  6. 盲目地将所有袜子与其邻居配对(不要打包)
  7. 查找所有匹配的对,打包并将打包对移动到“匹配”堆;  如果没有新的匹配 - 将“index”增加1
  8. 如果“index”大于2(这可能是取决于袜子的值  因为袜子数量越多,机会就越少   盲目地配对他们)去11
  9. 随机播放
  10. 转到1
  11. 忘记“索引”
  12. 选一个袜子
  13. 找到它的一对
  14. 如果袜子没有配对,请将其移至“缺失”桩
  15. 如果找到匹配对,请将对并将其移至“匹配”桩
  16. 如果还有一个袜子还有12个
  17. 如果只剩下一个则转到14
  18. 微笑满意:)
此外,还可以添加检查损坏的袜子,就像删除那些。它可以插入2到3之间,以及13到14之间。 我期待着听到任何经历或更正。

lest

赞同来自:

这是基于比较的模型的Omega(n log n)下限。 (唯一有效的操作是比较两个袜子。) 假设您知道您的2n袜子是这样排列的: p 1 p 2 p 3 ... p n p f(1) p f(2) ... p f(n) 其中f是集合{1,2,...,n}的未知排列。知道这一点不能使问题更难。有n!可能的输出(第一和第二半之间的匹配),这意味着您需要log(n!)= Omega(n log n)比较。这可以通过分类获得。 由于您对元素清晰度问题的连接感兴趣:证明元素清晰度的Omega(n log n)绑定更难,因为输出是二进制是/否。这里,输出必须是匹配的,并且可能的输出数量足以获得合适的界限。但是,有一个变量连接到元素清晰度。假设你有2n袜子,并想知道它们是否可以独特配对。您可以通过发送( 1 2 ,..., n )(a )从ED中减少1 1 2 2 ,..., n ,一个<子>名词)。 (顺便说一下,ED的硬度证明非常有趣,via topology。) 如果你只允许进行相等测试,我认为应该有一个Omega(n 2 )绑定原始问题。我的直觉是:考虑一个在测试后添加边缘的图形,并认为如果图形不密集,则输出不是唯一确定的。

hea

赞同来自:

如果“移动”操作相当昂贵,并且“比较”操作便宜,并且您需要将整个集合移动到缓冲区中,其中搜索比原始存储快得多...只需将排序集成到强制中移动。 我发现将分拣过程整合到悬挂干燥使其变得轻而易举。无论如何我需要拿起每个袜子,然后把它挂起来(移动)而且我没有任何东西把它挂在琴弦上的特定位置。现在只是不强制搜索整个缓冲区(字符串)我选择按颜色/阴影放置袜子。更深的左,更亮的右边,更丰富多彩的前面等等。现在,在我挂下每个袜子之前,如果已经匹配的那个,我会在它的“正确的附近”看 - 这限制了“扫描”到2-3个其他袜子 - 如果它是,我把另一个挂在它旁边。然后我将它们成对成对,同时在干燥时从琴弦中取出。 现在这可能与顶部答案提出的“按颜色形成桩”有所不同,但首先,通过不选择离散桩而是范围,我可以分类“紫色”是否变为“红色”或“蓝色”堆;它介于两者之间。然后通过集成两个操作(挂起和排序),挂起的排序开销就像单独排序的10%。

funde

赞同来自:

每当你拿起袜子,把它放在一个地方。然后你拿起的下一个袜子,如果它与第一个袜子不匹配,则将它放在第一个袜子旁边。如果有,那就有一对。这样,它有多少组合并不重要,每个袜子只有两种可能性 - 要么它已经在你的袜子阵列中,要么它没有,这意味着你将其添加到数组中的某个位置。 这也意味着你几乎肯定不会在阵列中拥有所有袜子,因为袜子会在匹配时被移除。

tqui

赞同来自:

已经提出了排序解决方案,但排序有点过多:我们不需要订单;我们只需要平等团体。 因此散列就足够了(而且速度更快)。

  1. 对于每种颜色的袜子,形成一堆。迭代输入篮中的所有袜子并将它们分配到颜色堆上。
  2. 迭代每一堆并通过其他一些指标(例如模式)将其分配到第二组桩中
  3. 递归应用此方案,直到您将所有袜子分布到可立即直观处理的非常小的桩上
当需要在大型数据集上散列连接或散列聚合时,这种递归散列分区实际上是由SQL Server完成的。它将构建输入流分配到许多独立的分区中。该方案线性地扩展到任意数量的数据和多个CPU。 如果您可以找到提供足够桶的分配密钥(散列密钥),并且每个桶足够小以便快速处理,则不需要递归分区。不幸的是,我不认为袜子有这样的属性。 如果每个袜子都有一个名为“PairID”的整数,可以根据PairID % 10(最后一位数)轻松地将它们分配到10个桶中。 我能想到的最好的真实世界分区是创建一个桩的矩形:一个是颜色,另一个是图案。为什么是矩形?因为我们需要O(1)随机访问桩。 (3D cuboid也可以使用,但这不太实用。)
更新: 那么并行性呢?多个人可以更快地匹配袜子吗?
  1. 最简单的平行策略是让多个工人从输入篮中取出并将袜子放在桩上。这只能扩大到这么多 - 想象有100人战斗超过10桩。同步成本(表现为手部碰撞和人工通信)会破坏效率并加速(参见Universal Scalability Law!)。这容易出现死锁吗?不,因为每个工人一次只需要访问一堆。只有一个“锁定”就不会出现死锁。活锁可能是可能的,取决于人类如何协调对桩的访问。他们可能只是使用random backoff,就像物理级别上的网卡一样,可以确定哪些卡可以独占访问网络线。如果适用于NICs,它也适用于人类。
  2. 如果每个工人都有自己的一堆桩,它几乎无限地扩展。然后,工人可以从输入篮中取出大块袜子(很少有争议,因为他们很少这样做)并且在分配袜子时它们不需要同步(因为它们具有线程局部桩)。最后,所有工人都需要将他们的桩组合在一起。我相信如果工人组成聚合树,可以在O(log(工人数量*每个工人的数量))中完成。
element distinctness problem怎么样?正如文章所述,元素清晰度问题可以在O(N)中解决。对于袜子问题也是如此(如果你只需要一个分配步骤,那么O(N)也是如此(我提出了多个步骤只是因为人类在计算上很糟糕 - 如果你在md5(color, length, pattern, ...)上分发,那么一步就足够了,即所有属性的完美哈希) )。 显然,人们不能比O(N)更快,所以我们已达到最佳下限。 虽然输出不完全相同(在一种情况下,只是一个布尔值。在另一种情况下,袜子对),渐近复杂性是相同的。

bmagni

赞同来自:

为了说明从一堆袜子配对的效率,我们必须首先定义机器,因为配对不是通过图灵也不是通过随机访问机器来完成的,这通常被用作一个基础。算法分析。

机器 机器是一个被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中读取。我们的机器模型能够通过使用2个臂来操纵环境。使用我们的大脑计算逻辑和算术运算(希望;-))。 我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时。由于物理限制,由手臂或眼睛执行的操作具有非恒定的时间复杂度。这是因为我们不能用胳膊移动无休止的大堆袜子,也不能用眼睛看到无休止的大堆袜子上的袜子。 然而,机械物理学给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以立刻移动它们中的一对。 因此,根据以前的分析,操作应按降序使用:
  • 逻辑和算术运算
  • 环境读取
  • 环境修改
我们还可以利用人们只有非常有限的袜子这一事实。所以环境修改可能涉及堆中的所有袜子。

算法 所以这是我的建议:
  1. 将所有袜子堆放在地板上。
  2. 通过查看地板上的袜子找到一双。
  3. 从2开始重复,直到不能成对。
  4. 从1开始重复,直到地板上没有袜子。
操作4是必要的,因为当将袜子散布在地板上时,一些袜子可能隐藏其他袜子。以下是对算法的分析:

分析 该算法以高概率终止。这是因为在步骤2中无法找到成对的袜子。 对于配对n袜子对的以下运行时分析,我们假设在步骤1之后至少有一半的2n袜子未被隐藏。因此在一般情况下我们可以找到n/2对。这意味着循环是步骤4执行O(log n)次。执行步骤2 O(n^2)次。所以我们可以得出结论:
  • 该算法涉及O(ln n + n)环境修改(步骤1 O(ln n)加上从地板上挑选每一双袜子)
  • 该算法涉及来自步骤2的O(n^2)环境读取
  • 该算法涉及O(n^2)逻辑和算术运算,用于在步骤2中将袜子与另一个袜子进行比较
因此,我们的总运行时复杂度为O(r*n^2 + w*(ln n + n)),其中rw分别是针对合理数量的袜子的环境读取和环境写入操作的因素。省略了逻辑和算术运算的成本,因为我们假设需要一定量的逻辑和算术运算来决定2个袜子是否属于同一对。这在每种情况下都可能不可行。

id_sed

赞同来自:

你正试图解决错误的问题。 解决方案1:每次将脏袜子放入洗衣篮时,请将它们系在一起。这样你洗完后就不用做任何分类了。可以把它想象成在Mongo数据库中注册索引。未来可以节省一些CPU。 解决方案2:如果是冬天,你不必穿袜子。我们是程序员。只要它有效,没有人需要知道。 解决方案3:传播工作。您希望异步执行这样一个复杂的CPU进程,而不会阻止UI。把那堆袜子塞进一个袋子里。只在需要时寻找一对。这样,它所需的工作量就不那么明显了。 希望这可以帮助!

fillum

赞同来自:

我所做的就是拿起第一只袜子并将其放下(比如说,放在洗衣盆的边缘)。然后我拿起另一只袜子,检查它是否和第一只袜子一样。如果是,我将它们都删除。如果不是,我把它放在第一个袜子旁边。然后我拿起第三个袜子并将其与前两个比较(如果它们仍在那里)。等等。 这种方法可以很容易地在一个数组中实现,假设“删除”袜子是一个选项。实际上,你甚至不需要“删除”袜子。如果你不需要对袜子进行分类(见下文),那么你可以只是移动它们,最后得到一个阵列,它在阵列中成对排列所有袜子。 假设socks的唯一操作是比较相等,这个算法基本上仍然是一个n 2 算法,虽然我不知道平均情况(从未学会计算)。 排序当然可以提高效率,特别是在现实生活中,您可以轻松地在另外两个袜子之间“插入”袜子。在计算中,同样可以通过树来实现,但这是额外的空间。而且,当然,我们回到NlogN(或者更多,如果有几个袜子通过排序标准相同,但不是来自同一对)。 除此之外,我无法想到任何事情,但这种方法在现实生活中看起来确实非常有效。 :)

zamet

赞同来自:

当我对袜子进行分类时,我会做一个近似的radix sort,在相同颜色/图案类型的其他袜子附近放下袜子。除非我能看到在该位置/附近的精确匹配,我即将放下袜子,我在那时提取该对。 几乎所有其他算法(包括the top scoring answer by usr)排序,然后删除对。我发现,作为一个人,最好尽量减少一次考虑的袜子数量。 我是这样做的:

  1. 挑选一条与众不同的袜子(无论什么东西首先抓住我的眼睛)。
  2. 从该概念位置开始基数排序,方法是根据与该组相似的方式从堆中拉出袜子。
  3. 将新袜子放置在当前堆中,距离基于它的不同程度。如果你发现自己把袜子放在另一个上面,因为它是相同的,在那里形成一对,并将它们移除。这意味着未来的比较将花费更少的精力来找到正确的位置。
这利用了人类在O(1)时间内模糊匹配的能力,这在某种程度上等同于在计算设备上建立散列映射。 通过首先拉出独特的袜子,您可以留出空间来“放大”开始时不那么与众不同的特征。 在消除了fluro彩色,带有条纹的袜子和三双长袜之后,你可能最终会得到大多数白色袜子,大致按它们的磨损程度排序。 在某些时候,袜子之间的差异足够小,以至于其他人不会注意到差异,并且不需要任何进一步的匹配工作。

a_et

赞同来自:

我已经采取了简单的步骤来减少我花费O(1)时间的过程。 通过减少我对两种袜子中的一种(白色袜子用于娱乐,黑色袜子用于工作)的投入,我只需要确定我手中的两个袜子中的哪一个。 (从技术上讲,因为它们永远不会一起洗,所以我将过程缩短为O(0)时间) 需要一些前期工作才能找到合适的袜子,并购买足够数量的袜子以消除对现有袜子的需求。正如我在需要黑色袜子之前做的那样,我的努力很小,但里程可能会有所不同。 在非常流行和有效的代码中已经多次看到过这种前期努力。例子包括#define'pi到几个小数(其他例子存在,但那是现在想到的那个)。

tiste

赞同来自:

我希望我能为这个问题贡献一些新东西。我注意到所有答案都忽略了这样一个事实,即有两个点可以执行预处理,而不会降低整体洗衣性能。 此外,即使是大家庭,我们也不需要承担大量的袜子。袜子被从抽屉中取出并被磨损,然后被丢弃在他们停留的地方(可能是垃圾箱),然后再被洗涤。虽然我不会把所谓的bin称为LIFO-Stack,但我认为这是可以安全的

  1. 人们将他们的袜子大致扔在同一个区域 仓,
  2. bin在任何时候都没有随机化,因此
  3. 从此bin顶部取得的任何子集通常都包含两者 一双袜子。
由于我所知道的所有洗衣机的尺寸都有限(无论你要洗多少袜子),洗衣机实际随机化,无论我们有多少袜子,我们总是有小的子集,几乎没有单身。 我们的两个预处理阶段是“将袜子放在晾衣绳上”和“从晾衣绳上取袜子”,我们必须这样做,以便得到不仅干净,而且干燥的袜子。和洗衣机一样,clothelines也是有限的,我认为我们拥有整条线,我们可以看到袜子。 这是put_socks_on_line()的算法:
while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}
不要浪费你的时间移动袜子或寻找最佳匹配,这一切都应该在O(n)中完成,我们还需要将它们放在未分类的线上。 袜子尚未配对,我们在线上只有几个相似性簇。在这里我们有一套有限的袜子是有帮助的,因为这有助于我们创造“好”的簇(例如,如果袜子组中只有黑色袜子,按颜色聚类不是要走的路) 这是take_socks_from_line()的算法:
while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put sock in basket
 }
我应该指出,为了提高剩余步骤的速度,明智的做法是不要随机挑选下一个袜子,而是在每个簇的袜子后连续袜子。 两个预处理步骤都不需要花费更多的时间,而不仅仅是将袜子放在生产线上或篮子里,无论如何我们必须这样做,所以这应该可以大大提高洗衣性能。 在此之后,很容易做出散列分区算法。通常,大约75%的袜子已经配对,留给我一小部分袜子,这个子集已经(有些)聚集(在预处理步骤后我没有在我的篮子中引入太多熵)。另一件事是剩下的集群往往足够小,可以立即处理,因此可以从篮子中取出整个集群。 这是sort_remaining_clusters()的算法:
while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}
在那之后,只剩下几个袜子。这是我将以前未配对的袜子引入系统并处理剩余袜子而没有任何特殊算法的地方 - 剩下的袜子非常少,可以在视觉上非常快速地加工。 对于所有剩余的袜子,我假设它们的对应物仍未洗涤并将它们放在下一次迭代中。如果你随着时间的推移注册了不成对袜子的增长(“袜子泄漏”),你应该检查你的垃圾箱 - 它可能会被随机化(你有猫在那里睡觉吗?) 我知道这些算法需要很多假设:一个垃圾箱,它可以作为某种LIFO堆栈,一个有限的普通洗衣机,以及一条有限的正常晾衣绳 - 但这仍适用于大量的袜子。 关于并行性: 只要您将两个袜子扔进同一个垃圾箱,您就可以轻松地将所有这些步骤并行化。

prem

赞同来自:

排序你的n双袜子的问题是O(n)。在将它们扔进洗衣篮之前,将左边的一个拧到右边的那个。取出它们后,你切断了线程并将每一对放入你的抽屉 - 在n对上进行2次操作,所以O(n)。 现在接下来的问题就是你是否自己洗衣服,而你的妻子是自己洗衣服。这可能是一个完全不同的问题领域的问题。 :)

jalias

赞同来自:

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

  • 选择其中一只袜子并将其丢弃(为该对创建'桶')
  • 如果下一个是前一个对,则将其放入现有存储桶,否则创建一个新存储桶。
在最坏的情况下,这意味着您将拥有n / 2个不同的桶,并且您将确定哪个桶包含当前袜子对的n-2个桶。显然,如果你只有几对,这个算法效果很好;我做了12对。 它不是那么科学,但它运作良好:)

dsed

赞同来自:

考虑一个大小为“N”的哈希表。 如果我们假设正态分布,那么至少有一个袜子映射到一个桶的“插入”的估计数量是NlogN(即,所有桶都已满) 我把它作为另一个谜题的一部分,但我很高兴被证明是错误的。 Here's my blog article on the same 设'N'对应于您拥有的独特颜色数量/袜子数量的近似上限。 一旦发生碰撞(a.k.a:匹配),只需移除那双袜子即可。  对下一批NlogN袜子重复相同的实验。 它的美妙之处在于,由于人类思维的运作方式,你可以进行NlogN并行比较(碰撞解决)。 :-)

jculpa

赞同来自:

我建议的解决方案假设除了颜色外,所有袜子的细节都相同。如果有更多细节要在袜子之间推迟,这些细节可以用来定义不同类型的袜子而不是我的例子中的颜色。 鉴于我们有一堆袜子,袜子可以有三种颜色:蓝色,红色或绿色。 然后我们可以为每种颜色创建一个并行工作者;它有自己的列表来填充相应的颜色。

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

est_ut

赞同来自:

理论极限是O(n),因为你需要触摸每个袜子(除非一些已经以某种方式配对)。 您可以使用radix sort实现O(n)。您只需要为存储桶选择一些属性。

  1. 首先你可以选择(她的,我的) - 将它们分成两堆,
  2. 然后使用颜色(可以对颜色有任何顺序,例如按颜色名称按字母顺序排列) - 按颜色将它们分成堆(记住保持同一堆中所有袜子的步骤1的初始顺序),
  3. 然后是袜子的长度,
  4. 然后纹理, ....
如果您可以选择有限数量的属性,但有足够的属性可以唯一地标识每对,那么您应该在O(k * n)中完成,如果我们认为k是有限的,则为O(n)。