0

我有以下需要快速算法解决的问题：假设我们有两组数据 Group1 和 Group2，它们都是由笛卡尔坐标中的点组成的。任一数据组中的点数相等，数据组中点的顺序也是固定的。现在，Group1 和 Group2 中的每个点将被分类为不同的类别。例如，Group1 中的第一个数据将被分类为， Group1Class1Group2 中的第一个数据将被分类为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;
}
4

2 回答 2

1

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

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

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
于 2013-07-22T15:48:29.070 回答
0

制作两个列表的副本，每个列表都按类别排序。匹配两个排序列表的对应元素。

对于合适的排序算法，此解决方案是 O(n log n)。而且，它把大部分工作都放在了排序中，很容易找到高度优化的排序代码。

于 2013-07-22T15:53:33.670 回答