해당 쌍 검색

Question

해결해야 할 빠른 알고리즘이 필요한 다음과 같은 문제가 있습니다. 그룹 1과 그룹 2의 두 그룹이 직교 좌표의 점으로 구성되어 있다고 가정합니다. 데이터 그룹 중 하나의 포인트 수는 동일하고 데이터 그룹의 포인트 시퀀스도 고정됩니다. 이제 그룹 1과 그룹 2의 각 포인트는 서로 다른 클래스로 분류됩니다. 예를 들어 Group1의 첫 번째 데이터는 Group1Class1으로 분류되고 Group2의 첫 번째 데이터는 으로 분류되며 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

모든 저장의지도를 사용할 수 있습니다 다음과 같이 제안을 바탕으로

는

, 작업을하는 두 번째 방법은 첫 번째 그룹의 요소

두 번째 그룹에서 한 루프 이상 맵에 항목이 있는지 확인하고 존재하는 경우 그룹 번호를 가져 와서 결과 세트에 추가하십시오.

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

두 목록을 각각 클래스별로 정렬하여 복사하십시오. 두 개의 정렬 된 목록의 해당 요소를 일치시킵니다.

이 솔루션은 적절한 정렬 알고리즘의 경우 O (n log n)입니다. 또한, 대부분의 작업을 일종의 형식으로 처리하므로 고도로 최적화 된 정렬 코드를 쉽게 찾을 수 있습니다.