Найдите аналогичные расстояния между всеми значениями в векторном и подмножестве

Question

Представляет собой вектор с двойными значениями. Я хочу знать, какие расстояния между любыми элементами этого вектора имеют одинаковое расстояние друг к другу. В лучшем случае результатом является вектор подмножеств исходных значений, где подмножества должны иметь не менее n членов.

//given 
vector<double> values = {1,2,3,4,8,10,12}; //with simple values as example 

//some algorithm 

//desired result as: 
vector<vector<double> > subset; 
//in case of above example I would expect some result like: 
//subset[0] = {1,2,3,4}; //distance 1 
//subset[1] = {8,10,12}; //distance 2 
//subset[2] = {4,8,12}; // distance 4 
//subset[3] = {2,4}; //also distance 2 but not connected with subset[1] 
//subset[4] = {1,3}; //also distance 2 but not connected with subset[1] or subset[3] 
//many others if n is just 2. If n is 3 (normally the minimum) these small subsets should be excluded. 

Этот пример упрощается, поскольку расстояния целых чисел могут быть итеративны и испытаны для вектора, который не относится к двойному или поплавку.

Моя идея до сих пор

Я думал, что-то вроде вычисления расстояния и хранить их в векторе. Создание матрицы разностных расстояний и порог этой матрицы для некоторого допуска для аналогичные расстояния.

//Calculate distances: result is a vector 
vector<double> distances; 
for (int i = 0; i < values.size(); i++) 
    for (int j = 0; j < values.size(); j++) 
    { 
     if (i >= j) 
      continue; 
     distances.push_back(abs(values[i] - values[j])); 
    } 
//Calculate difference of these distances: result is a matrix 
Mat DiffDistances = Mat::zero(Size(distances.size(), distances.size()), CV_32FC1); 
for (int i = 0; i < distances.size(); i++) 
    for (int j = 0; j < distances.size(); j++) 
    { 
     if (i >= j) 
      continue; 
     DiffDistances.at<float>(i,j) = abs(distances[i], distances[j]); 
    } 
//threshold this matrix with some tolerance in difference distances 
threshold(DiffDistances, DiffDistances, maxDistTol, 255, CV_THRESH_BINARY_INV); 
//get points with similar distances 
vector<Points> DiffDistancePoints; 
findNonZero(DiffDistances, DiffDistancePoints); 

На данный момент я застрял в поиске исходных значений, соответствующих моим аналогичным расстояниям. Их должно быть возможно найти, но, похоже, очень сложно отследить индексы, и мне интересно, нет ли более простого способа решить проблему.

Answer 1

Это решение, которое работает, если нет веток, что нет значений ближе друг к другу, чем 2*threshold. Это действительная соседняя область, потому что соседние облигации должны отличаться меньше порога, если я правильно понял @Phann.

Решение окончательно не является самым быстрым и самым приятным решением. Но вы можете использовать его в качестве отправной точки:

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main(){ 
    std::vector<double> values = {1,2,3,4,8,10,12}; 
    const unsigned int nValues = values.size(); 
    std::vector< std::vector<double> > distanceMatrix(nValues - 1); 
    // The distanceMatrix has a triangular shape 
    // First vector contains all distances to value zero 
    // Second row all distances to value one for larger values 
    // nth row all distances to value n-1 except those already covered 
    std::vector< std::vector<double> > similarDistanceSubsets; 
    double threshold = 0.05; 

    std::sort(values.begin(), values.end()); 

    for (unsigned int i = 0; i < nValues-1; ++i) { 
     distanceMatrix.at(i).resize(nValues-i-1); 
     for (unsigned j = i+1; j < nValues; ++j){ 
      distanceMatrix.at(i).at(j-i-1) = values.at(j) - values.at(i); 
     } 
    } 

    for (unsigned int i = 0; i < nValues-1; ++i) { 
     for (unsigned int j = i+1; j < nValues; ++j) { 
      std::vector<double> thisSubset; 
      double thisDist = distanceMatrix.at(i).at(j-i-1); 

      // This distance already belongs to another cluster 
      if (thisDist < 0) continue; 

      double minDist = thisDist - threshold; 
      double maxDist = thisDist + threshold; 
      thisSubset.push_back(values.at(i)); 
      thisSubset.push_back(values.at(j)); 
      //Indicate that this is already clustered 
      distanceMatrix.at(i).at(j-i-1) = -1; 

      unsigned int lastIndex = j; 
      for (unsigned int k = j+1; k < nValues; ++k) { 
       thisDist = distanceMatrix.at(lastIndex).at(k-lastIndex-1); 

       // This distance already belongs to another cluster 
       if (thisDist < 0) continue; 

       // Check if you found a new valid pair 
       if ((thisDist > minDist) && (thisDist < maxDist)){ 
        // Update the valid distance interval 
        minDist = thisDist - threshold; 
        minDist = thisDist - threshold; 
        // Add the newly found point 
        thisSubset.push_back(values.at(k)); 
        // Indicate that this is already clustered 
        distanceMatrix.at(lastIndex).at(k-lastIndex-1) = -1; 
        // Continue the search from here 
        lastIndex = k; 
       } 
      } 
      if (thisSubset.size() > 2) { 
       similarDistanceSubsets.push_back(thisSubset); 
      } 
     } 
    } 
    for (unsigned int i = 0; i < similarDistanceSubsets.size(); ++i) { 
     for (unsigned int j = 0; j < similarDistanceSubsets.at(i).size(); ++j) { 
      std::cout << similarDistanceSubsets.at(i).at(j); 
      if (j != similarDistanceSubsets.at(i).size()-1) { 
       std::cout << " "; 
      } 
      else { 
       std::cout << std::endl; 
      } 
     } 
    } 
} 

Идея состоит в том, чтобы предвычисления расстояния, а затем искать для каждой пары частиц, начиная от самых маленьких и его больших соседей, если есть другой действительный пара над ним , Если так, все они собираются в подмножестве, и это добавляется к вектору подмножества. Для каждого нового значения действительный соседний регион должен быть обновлен, чтобы гарантировать, что соседние расстояния отличаются меньшим пороговым значением. Впоследствии программа продолжает следующую минимальную ценность и ее более крупные соседи и так далее.

Answer 2

Ниже приведен алгоритм, который немного отличается от вашего, это O(n^3) в длину n из вектор - не очень эффективен.

Он основан на предпосылке, что вы хотите иметь подмножества не менее размера 2. Таким образом, вы можете рассмотреть все двухэлементные подмножества вектора, а затем найти все остальные элементы, которые также совпадают.

Так задана функция

std::vector<int> findSubset(std::vector<int> v, int baseValue, int distance) { 
    // Find the subset of all elements in v that differ by a multiple of 
    // distance from the base value 
} 

вы можете сделать

std::vector<std::vector<int>> findSubsets(std::vector<int> v) { 
    for(int i = 0; i < v.size(); i++) { 
    for(int j = i + 1; j < v.size(); j++) { 
     subsets.push_back(findSubset(v, v[i], abs(v[i] - v[j]))); 
    } 
    } 

    return subsets; 
} 

только оставшаяся проблема отслеживания дубликатов, может быть, вы можете сохранить список хэшированного (baseValue % distance, distance) пар для все подмножества, которые вы уже нашли.