正在搜索相應的對

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

如果我假設整數無法駐留在多個組可以使用地圖來存儲所有第一組中的元素。

比第二組中的一個循環檢查地圖中是否存在項目，如果存在 - 獲取它的組編號並將其添加到結果集中。

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）。而且，它將大部分工作放在了一起，並且很容易找到高度優化的排序代碼。