Searching for corresponding pairs

Question

I have the following problem that needs a quick algorithm to solve: suppose we have two groups of data Group1 and Group2, both of which are composed of points in the Cartesian coordinate. The number of points in either of the data groups is equal, and the sequence of points in the data group is also fixed. Now, one by one each point in Group1 and Group2 will be classified into different classes. For example the first data in Group1 will be classified as Group1Class1 and the first data in Group2 will be classified as Group2Class1, the second data in Group1 will be classified as Group1Class2 and the second data in Group2 may be classified as Group2Class2. It may happen the same sequence of data in both data groups belongs to different classes. For instance, the 10th data in Group1 may be classsifed as Group1Class2 while the 10th data in Group2 may be classified as Group2Class10. Finally, we can have the following classes and data index in these data groups:

   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}

What I am going to do is to find the corresponding class pairs if the same data sequence appears. For example, in the above example, the corresponding class pairs are as follows:

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

I have written the following codes to do the task:

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

It seems that the function could work, but I am not sure that this is a smart way of doing the job. Any idea will be appreciated.

Based on the suggestions, the second way of doing the job is as follows:

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

If I assume an integer can't reside in more than one group you can use a map of to store all the elements in the first group.

Than with one loop over the second group check an item exists in the map, and if it exist - get it's group number and add it to the result set.

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

Answer 2

Make copies of the two lists, each sorted by class. Match corresponding elements of the two sorted lists.

This solution is O(n log n) for a suitable sort algorithm. Moreover, it puts most of the work in the sort, and it is easy to find highly optimized sort code.