Блог

У меня есть последовательность [-1, -2, -3, -4,0,1,2,3], и задача состоит в том, чтобы достичь целевой последовательности [1,2,3,0,-1,-2,-3,-4]. Символ «0» означает пробел — его можно заменить на символ без пробелов, подобный этому: [-1,-2,-3,-4,1,0,2,3]. При каждой манипуляции с начальной последовательностью стоимость равна 0 (нулю). Мне нужно знать коэффициент того, насколько близка каждая последующая последовательность к целевой последовательности. Это может быть значение в диапазоне [0.0 — 1.0], где 1.0 означает последовательность целей, а 0.0 означает начальную последовательность, или это может быть значение хэш-кода типа INTEGER, но это значение должно быть меньше и меньше при каждом подходе к последовательности целей. Есть идеи, как это реализовать? Я пробовал алгоритмы сравнения строк (редактировать расстояние), но они не работают для этого случая.

Предполагая, что все числа уникальны.

Впереди непроверенный код

 using SumType = int64_t; // feel free to shoot yourself in the foot by using floats.
SumType PosSum(const std::vector<int>amp; curr, const std::vector<int>amp; goal) {
  SumType sum = 0;
  for(auto it = curr.begin(); it != curr.end();   it) {
    // if (*it != gabValue) ???
    sum  = std::abs(std::distance(it, std::find(goal.begin(), goal.end(), *it));
  }
}
 

Альтернативное использование std::unordered_map для хранения позиций целей может быть быстрее.

 auto init = PosSum(start, goal);
if (init == 0)
  return;

...whatever

auto now = PosSum(current, goal); // slight problem as init is not guaranteed to be a global minima.

auto coeff = double(1.0) - double(now)/double(init); // which makes this [x:1] where x can be zero or negative