c++ - 搜索对应的对

Question

我有以下问题需要一个快速算法来解决:假设我们有两组数据Group1和Group2，它们都是由笛卡尔坐标中的点组成的。任一数据组中的点数相等，数据组中点的顺序也是固定的。现在，Group1和Group2中的每个点将被一一分类到不同的类中。例如Group1中的第一个数据将被分类为Group1Class1，Group2中的第一个数据将被分类为Group2Class1，Group1中的第二个数据将被分类为 Group1Class2和Group2中的第二个数据可以归类为Group2Class2。它可能发生在两个数据组中的相同数据序列属于不同的类。例如，Group1 中的第 10 个数据可能被分类为 Group1Class2，而 Group2 中的第 10 个数据可能被分类为 Group2Class10。最后，我们可以在这些数据组中有如下类和数据索引:

   Class            Data index
Group1Class1        {1 2 3}
Group1Class2        {4 5 6 7}
Group1Class3        {8}
Group1Class4        {9}
Group1Class5        {10 11}
Group1Class6        {12}


   Class            Data index
Group2Class1        {1 2}
Group2Class2        {3}
Group2Class3        {4 5 6 7 8 9}
Group2Class4        {10 11 12}

我要做的是如果出现相同的数据序列，就找到对应的类对。比如上面的例子，对应的类对如下:

Group1Class1   Group2Class1
Group1Class1   Group2Class2
Group1Class2   Group2Class3
Group1Class3   Group2Class3
Group1Class4   Group2Class3
Group1Class5   Group2Class4
Group1Class6   Group2Class4

我编写了以下代码来完成任务:

int main()
{ 
    std::vector<std::vector<int> > map_array_left;
    std::vector<int> temp;
    temp.push_back(1);
    temp.push_back(2);
    temp.push_back(3);
    map_array_left.push_back( temp);

    temp.clear();
    temp.push_back(4);
    temp.push_back(5);
    temp.push_back(6);
    temp.push_back(7);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(8);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(9);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(10);
    temp.push_back(11);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(12);
    map_array_left.push_back(temp);


    std::vector<std::vector<int> > map_array_right;
    temp.clear();
    temp.push_back(1);
    temp.push_back(2);
    map_array_right.push_back(temp);

    temp.clear();
    temp.push_back(3);
    map_array_right.push_back(temp);;

    temp.clear();
    temp.push_back(4);
    temp.push_back(5);
    temp.push_back(6);
    temp.push_back(7);
    temp.push_back(8);
    temp.push_back(9);
    map_array_right.push_back(temp);;

    temp.clear();
    temp.push_back(10);
    temp.push_back(11);
    temp.push_back(12);
    map_array_right.push_back(temp);;


    std::vector<int> temp_right;
    std::vector<int> temp_left;
    std::vector<std::vector<int> > corresponding;
    for(int i=0; i<map_array_left.size(); i++)
    {

        temp_left = map_array_left[i];

        for (int j=0; j<map_array_right.size(); j++)
        {
            std::vector<int> cor_single;
            cor_single.push_back(i+1);
            temp_right = map_array_right[j];
            bool b_find = false;
            for(int k=0; k<temp_right.size();k++)
            {
                std::vector<int>::iterator it;
                it = find(temp_left.begin(),temp_left.end(),temp_right[k]);
                if(it == temp_left.end())
                {

                }
                else
                {
                    b_find = true;
                    break;
                }

            }
            if(b_find)
            {

                cor_single.push_back(j+1);
                corresponding.push_back(cor_single);
                cor_single.clear();
                cor_single.push_back(i+1);
            }


        }

    }



    return 0;
}

看起来这个功能可以工作，但我不确定这是完成这项工作的明智方式。任何想法将不胜感激。

根据建议，第二种做法如下:

void build_map(const std::vector<std::vector<int> > &map_array_left,map<int,int> &left_map)
{
    int class_index,data_index; 
    for(int i=0; i<map_array_left.size(); i++)
    {
        class_index = i+1;
        for(int j=0; j<map_array_left[i].size(); j++)
        {
            data_index = map_array_left[i][j];
            left_map.insert(std::pair<int,int>(data_index,class_index));
        }
    }
}

void find_correponding(const std::vector<std::vector<int> > &map_array_right,  std::map<int,int> &left_map,set<vector<int> > &correponding_classes)
{
    int class_index_left;
    int class_index_right;
    int data_index;
    for(int i=0; i<map_array_right.size(); i++)
    {

        class_index_right = i+1;

        for(int j=0; j<map_array_right[i].size(); j++)
        {
            vector<int> corresponding_single;
            data_index = map_array_right[i][j];
            class_index_left = left_map[data_index];
            corresponding_single.push_back(class_index_left);
            corresponding_single.push_back(class_index_right);
            correponding_classes.insert(corresponding_single);


        }
    }

}


int main()
{
    std::vector<std::vector<int> > map_array_left;
    std::vector<int> temp;
    temp.push_back(1);
    temp.push_back(2);
    temp.push_back(3);
    map_array_left.push_back( temp);

    temp.clear();
    temp.push_back(4);
    temp.push_back(5);
    temp.push_back(6);
    temp.push_back(7);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(8);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(9);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(10);
    temp.push_back(11);
    map_array_left.push_back(temp);

    temp.clear();
    temp.push_back(12);
    map_array_left.push_back(temp);


    std::vector<std::vector<int> > map_array_right;
    temp.clear();
    temp.push_back(1);
    temp.push_back(2);
    map_array_right.push_back(temp);

    temp.clear();
    temp.push_back(3);
    map_array_right.push_back(temp);;

    temp.clear();
    temp.push_back(4);
    temp.push_back(5);
    temp.push_back(6);
    temp.push_back(7);
    temp.push_back(8);
    temp.push_back(9);
    map_array_right.push_back(temp);;

    temp.clear();
    temp.push_back(10);
    temp.push_back(11);
    temp.push_back(12);
    map_array_right.push_back(temp);;

    map<int,int> left_map;

    build_map( map_array_left, left_map);

    std::set<vector<int> > correponding_classes;

    find_correponding(map_array_right,left_map,correponding_classes);







    return 0;
}

Answer 1

如果我假设一个整数不能驻留在多个组中，您可以使用 的映射来存储第一组中的所有元素。

然后在第二组上循环检查 map 中是否存在一个项目，如果存在 - 获取它的组号并将其添加到结果集中。

std::map<int,int> myMap;

myMap[1]=1;
myMap[2]=1;
myMap[3]=1;
myMap[4]=2;
myMap[5]=2;
myMap[6]=2;
myMap[7]=2;
// ...

// Check if 1 exists in the map    
if (myMap[1])
// match of myMap[1] and the group number you are checking
else
// No match