我有一个序列[-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; // 随意使用浮点数来给自己找麻烦。
SumType PosSum(const std::vector<int>& curr, const std::vector<int>& 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); // 有一点问题，因为init不保证是全局最小值。
auto coeff = double(1.0) - double(now)/double(init); // 这使得[x:1]其中x可以是零或负数